Tally NP sets and easy census functions.
From MaRDI portal
Publication:1854340
DOI10.1006/inco.1999.2810zbMath1046.68538OpenAlexW2015665482MaRDI QIDQ1854340
Jörg Rothe, Judy Goldsmith, Ogihara, Mitsunori
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
Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items (3)
The complexity of counting self-avoiding walks in subgraphs of two-dimensional grids and hypercubes. ⋮ Closure and nonclosure properties of the classes of compressible and rankable sets ⋮ 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
This page was built for publication: Tally NP sets and easy census functions.
