The size of SPP
From MaRDI portal
Publication:596117
DOI10.1016/j.tcs.2004.02.029zbMath1068.68064OpenAlexW2053749801MaRDI QIDQ596117
Publication date: 10 August 2004
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2004.02.029
Related Items (3)
Unnamed Item ⋮ Martingale families and dimension in P ⋮ Baire categories on small complexity classes and meager-comeager laws
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- NP-hard sets are superterse unless NP is small
- Cook versus Karp-Levin: Separating completeness notions if NP is not small
- Weak completeness in \(\text{E}\) and \(\text{E}_{2}\)
- NP is as easy as detecting unique solutions
- Almost everywhere high nonuniform complexity
- Gap-definable counting classes
- Hardness vs randomness
- Almost every set in exponential time is P-bi-immune
- Observations on measure and lowness for \(\Delta_ 2^ p\)
- Complete distributional problems, hard languages, and resource-bounded measure
- The zero-one law holds for BPP
- Randomness vs time: Derandomization under a uniform assumption
- Relative to a random oracle, NP is not small
- MAX3SAT is exponentially hard to approximate if NP has positive dimension.
- Graph Isomorphism is in SPP
- Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses
- PP is as Hard as the Polynomial-Time Hierarchy
- Counting Classes are at Least as Hard as the Polynomial-Time Hierarchy
- Fine Separation of Average-Time Complexity Classes
- Measure, Stochasticity, and the Density of Hard Languages
- The Density of Weakly Complete Problems under Adaptive Reductions
- The Complexity and Distribution of Hard Problems
- Separating NP-completeness notions under strong hypotheses
- On pseudorandomness and resource-bounded measure
This page was built for publication: The size of SPP
