The enumerability of P collapses P to NC

No abstract is available for this paper.

• Publication year

  2005

• Venue

  Theoretical Computer Science

• Publication date

  2005-11-22

• Fields of study

  Mathematics, Physics, Computer Science

• Identifiers
  DOI 10.1016/j.tcs.2005.07.010
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• The (Non)Enumerability of the Determinant and the Rank

  2003cited by this paper
• Modern computer algebra

  2002cited by this paper
• Tally NP Sets and Easy Census Functions

  1998cited by this paper
• On membership comparable sets

  1998influential reference
• Resolution of Hartmanis' conjecture for NL-hard sparse sets

  1997cited by this paper
• Polynomial Factorization

  1996cited by this paper
• Limits to Parallel Computation: P-Completeness Theory

  1995cited by this paper
• Approximable sets

  1995cited by this paper
• Limits to parallel computation

  1995cited by this paper
• On finding the number of graph automorphisms

  1995cited by this paper
• Polynomial-time membership comparable sets

  1994cited by this paper
• Introduction to finite fields and their applications: Theoretical Applications of Finite Fields

  1994cited by this paper
• Polynomial Factorization Sharp Bounds, Efficient Algorithms

  1993cited by this paper
• Polynomial Factorization 1987-1991

  1992cited by this paper
• Reconstructing algebraic functions from mixed data

  1992influential reference
• Introduction to coding theory

  1992cited by this paper
• Computational and Algorithmic Problems in Finite Fields

  1992cited by this paper
• Inverting a Vandermonde Matrix in Minimum Parallel Time

  1991cited by this paper
• Boolean Circuits Versus Arithmetic Circuits

  1991cited by this paper
• Parallel Construction of Irreducible Polynomials

  1991cited by this paper
• On the Complexity of Ranking

  1990cited by this paper
• Some connections between bounded query classes and nonuniform complexity

  1990cited by this paper
• Very Fast Parallel Polynomial Arithmetic

  1989cited by this paper
• Enumerative counting is hard

  1988influential reference
• A fast parallel algorithm to compute the rank of a matrix over an arbitrary field

  1986cited by this paper
• A Taxonomy of Problems with Fast Parallel Algorithms

  1985influential reference
• Parallel algorithms for algebraic problems

  1983cited by this paper
• Relativized circuit complexity

  1983cited by this paper
• Fast parallel matrix and GCD computations

  1982influential reference
• The circuit value problem is log space complete for P

  1975cited by this paper
• On the Density of Families of Sets

  1972cited by this paper
• A combinatorial problem; stability and order for models and theories in infinitary languages.

  1972cited by this paper
• Chervonenkis: On the uniform convergence of relative frequencies of events to their probabilities

  1971cited by this paper

• No citing papers are available for this paper.