Enumerative counting is hard

An n-variable Boolean formula can have anywhere from 0 to 2/sup n/ satisfying assignments. The question of whether a polynomial-time machine, given such a formula, can reduce this exponential number of possibilities to a small number of possibilities is explored. Such a machine is called an enumerator, and it is proved that if there is a good polynomial-time enumerator for Hash P (i.e. one where the small set has at most O( mod f mod /sup 1-e/) numbers), then P=NP=P/sup Hash P/ and probabilistic polynomial time equals polynomial time. Furthermore, Hash P and enumerating Hash P are polynomial-time Turing equivalent.<<ETX>>

• Publication year

  1988

• Venue

  [1988] Proceedings. Structure in Complexity Theory Third Annual Conference

• Publication date

  1988-06-14

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1109/SCT.1988.5279
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Polynomial Terse Sets

  1988cited by this paper
• The polynomial time hierarchy collapses if the Boolean hierarchy collapses

  1988cited by this paper
• Complexity Measures for Public-Key Cryptosystems

  1988cited by this paper
• Self-Reducible, P-Selective, Near-Testable, and P-Cheatable Sets: The Effect of Internal Structure on the Complexity of a Set

  1987cited by this paper
• Algebraic methods in the theory of lower bounds for Boolean circuit complexity

  1987cited by this paper
• Random Oracles Separate PSPACE from the Polynomial-Time Hierarchy

  1987cited by this paper
• Is One NP Question as Powerful as Two

  1987cited by this paper
• With probability one, a random oracle separates PSPACE from the polynomial-time hierarchy

  1986cited by this paper
• Almost optimal lower bounds for small depth circuits

  1986cited by this paper
• Some Observations on the Connection Between Counting an Recursion

  1986cited by this paper
• Complexity and Structure

  1986cited by this paper
• The Complexity of Sparse Sets in P

  1986cited by this paper
• On Approximation Algorithms for #P

  1985influential reference
• Separating the Polynomial-Time Hierarchy by Oracles (Preliminary Version)

  1985cited by this paper
• Two remarks on the power of counting

  1983cited by this paper
• The NP-Completeness Column: An Ongoing Guide

  1982cited by this paper
• Parity, circuits, and the polynomial-time hierarchy

  1981influential reference
• On Counting Problems and the Polynomial-Time Hierarchy

  1980cited by this paper
• The Complexity of Enumeration and Reliability Problems

  1979cited by this paper
• The Complexity of Computing the Permanent

  1979cited by this paper
• On the Difference Between One and Many (Preliminary Version)

  1977cited by this paper
• Relative Complexity of Checking and Evaluating

  1976cited by this paper
• On some central problems in computational complexity

  1975cited by this paper
• Computational complexity of probabilistic Turing machines

  1974cited by this paper
• The complexity of theorem-proving procedures

  1971cited by this paper
• Introduction to Automata

  1968cited by this paper

• SIGACT News Complexity Theory Column

  2024cites this paper
• Complexity and Approximation: In Memory of Ker-I Ko

  2020cites this paper
• The Power of Self-Reducibility: Selectivity, Information, and Approximation

  2019cites this paper
• The Value of Help Bits in Randomized and Average-Case Complexity

  2014cites this paper
• Choosing, Agreeing, and Eliminating in Communication Complexity

  2010cites this paper
• Enumerations of the Kolmogorov function

  2006cites this paper
• Weak cardinality theorems†

  2005cites this paper
• The enumerability of P collapses P to NC

  2005influential citation
• On the reducibility of sets inside NP to sets with low information content

  2004cites this paper
• Gems in the Field of Bounded Queries

  2003cites this paper
• Some connections between bounded query classes and non-uniform complexity

  2003influential citation
• Logspace Optimisation Problems and their Approximation Properties

  2003cites this paper
• Weak Cardinality Theorems for First-Order Logic

  2003cites this paper
• The (Non)Enumerability of the Determinant and the Rank

  2003cites this paper
• Alternative Notions of Approximation and Space-Bounded Computations

  2003cites this paper
• Comparing Verboseness for Finite Automata and Turing Machines

  2002cites this paper
• Theory of Semi-Feasible Algorithms

  2002cites this paper
• On the Enumerability of the Determinant and the Rank

  2002cites this paper
• Optimal Series-Parallel Trade-offs for Reducing a Function to Its Own Graph

  2002cites this paper
• Towards a Cardinality Theorem for Finite Automata

  2002cites this paper
• Some Connections between Bounded Query Classes and Non-Uniform Complexity (Long Version)

  2000cites this paper
• The complexity of oddan

  2000cites this paper
• The complexity of ODDnA

  2000cites this paper
• The communication complexity of enumeration, elimination, and selection

  2000cites this paper
• Models and Computability: A Techniques Oriented Survey of Bounded Queries

  1999cites this paper
• Polynomial-Time Multi-Selectivity

  1999cites this paper
• Restrictive Acceptance Suffices for Equivalence Problems

  1999cites this paper
• Optimal Separations for Parallel versus Sequential Self-Checking: Parallelism Can Exponentially Incr

  1998cites this paper
• Tally NP Sets and Easy Census Functions

  1998cites this paper
• One help-bit doesn't help

  1998cites this paper
• On membership comparable sets

  1998cites this paper
• A Techniques-Oriented Survey of Bounded Queries

  1997cites this paper
• Gap-De nability as a Closure

  1996cites this paper
• Witness-Isomorphic Reductions and Local SearchSophie Fischer

  1996cites this paper
• On the Query Complexity of Sets

  1996cites this paper
• Easy sets and hard certificate schemes

  1995cites this paper
• The Power of the Middle Bit of a #P Function

  1995cites this paper
• On the Structure of Low Sets

  1995cites this paper
• Descriptive Complexity of #P Functions

  1995cites this paper
• Frequency computation and bounded queries

  1995cites this paper
• On finding the number of graph automorphisms

  1995influential citation
• Products and help bits in decision trees

  1994cites this paper
• The Polynomial Time Function Hierarchy

  1994cites this paper
• A Note on Set Bit Enumeration

  1994cites this paper
• Polynomial-time membership comparable sets

  1994cites this paper
• Gap-Definability as a Closure Property

  1993cites this paper
• Computing functions with parallel queries to NP

  1993cites this paper
• On the Power of Enumerative Counting

  1992cites this paper
• On the nonuniform complexity of the graph isomorphism problem

  1992cites this paper
• Set bit enumeration is hard

  1992influential citation
• Kolmogorov Complexity and its Applications

  1991cites this paper
• A Note on Enumarative Counting

  1991cites this paper
• Some connections between bounded query classes and nonuniform complexity

  1990cites this paper
• A survey on counting classes

  1990cites this paper
• Algorithms from complexity theory: polynomial-time operations for complex sets

  1990cites this paper
• Algorithms from Complexity Theory: Polynominal-Time Operations for Complex Sets

  1990cites this paper
• On the Complexity of Ranking

  1990cites this paper
• Complexity Theory Retrospective

  1990cites this paper
• On the power of parity polynomial time

  1989cites this paper
• Structure of Complexity Classes: Separations, Collapses, and Completeness

  1988cites this paper
• NP-hard Sets are P-Superterse Unless R = NP

  1988cites this paper
• The power of counting

  1988cites this paper