Tally NP sets and easy census functions.
From MaRDI portal
Publication:1854340
DOI10.1006/inco.1999.2810zbMath1046.68538MaRDI QIDQ1854340
Ogihara, Mitsunori, Judy Goldsmith, Jörg Rothe
Publication date: 14 January 2003
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1006/inco.1999.2810
68Q25: Analysis of algorithms and problem complexity
03D15: Complexity of computation (including implicit computational complexity)
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
Related Items
The complexity of counting self-avoiding walks in subgraphs of two-dimensional grids and hypercubes., The enumerability of P collapses P to NC
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The strong exponential hierarchy collapses
- The complexity of computing the permanent
- A note on enumerative counting
- Relations among MOD-classes
- On the complexity of ranking
- BPP and the polynomial hierarchy
- A low and a high hierarchy within NP
- On the construction of parallel computers from various basis of Boolean functions
- On counting and approximation
- Graph isomorphism is in the low hierarchy
- Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
- On sparse sets in NP-P
- Turing machines with few accepting computations and low sets for PP
- Relative complexity of checking and evaluating
- The polynomial-time hierarchy
- Boolean operations, joins, and the extended low hierarchy
- Gap-definable counting classes
- Upward separation for FewP and related classes
- Computation times of NP sets of different densities
- Scalability and the isomorphism problem
- Easy sets and hard certificate schemes
- Enumerative counting is hard
- Defying upward and downward separation
- A complexity theory for feasible closure properties
- The polynomial-time hierarchy and sparse oracles
- Parity, circuits, and the polynomial-time hierarchy
- PP is as Hard as the Polynomial-Time Hierarchy
- Limitations of the upward separation technique
- On Circuit-Size Complexity and the Low Hierarchy in NP
- On Restricting the Size of Oracles Compared with Restricting Access to Oracles
- Sparse sets in NP-P: EXPTIME versus NEXPTIME
- The Complexity of Enumeration and Reliability Problems
- Compression and Ranking
- Counting Classes are at Least as Hard as the Polynomial-Time Hierarchy
- On Isomorphisms and Density of $NP$ and Other Complete Sets
- Computational Complexity of Probabilistic Turing Machines
- A Downward Collapse within the Polynomial Hierarchy
- Unambiguous Computation: Boolean Hierarchies and Sparse Turing-Complete Sets
- Relativized Polynomial Time Hierarchies Having Exactly K Levels
- P-Printable Sets
- Tally languages and complexity classes
- On the power of parity polynomial time
- Counting classes: Thresholds, parity, mods, and fewness
