The size of SPP
From MaRDI portal
Publication:596117
Recommendations
Cites work
- scientific article; zbMATH DE number 1346358 (Why is no real title available?)
- scientific article; zbMATH DE number 559220 (Why is no real title available?)
- scientific article; zbMATH DE number 1048036 (Why is no real title available?)
- scientific article; zbMATH DE number 1072530 (Why is no real title available?)
- scientific article; zbMATH DE number 1072536 (Why is no real title available?)
- scientific article; zbMATH DE number 1104166 (Why is no real title available?)
- scientific article; zbMATH DE number 1500526 (Why is no real title available?)
- scientific article; zbMATH DE number 1559537 (Why is no real title available?)
- scientific article; zbMATH DE number 1405686 (Why is no real title available?)
- Almost every set in exponential time is P-bi-immune
- Almost everywhere high nonuniform complexity
- Complete distributional problems, hard languages, and resource-bounded measure
- Cook versus Karp-Levin: Separating completeness notions if NP is not small
- Counting Classes are at Least as Hard as the Polynomial-Time Hierarchy
- Fine Separation of Average-Time Complexity Classes
- Gap-definable counting classes
- Graph Isomorphism is in SPP
- Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses
- Hardness vs randomness
- MAX3SAT is exponentially hard to approximate if NP has positive dimension.
- Measure, Stochasticity, and the Density of Hard Languages
- NP is as easy as detecting unique solutions
- NP-hard sets are superterse unless NP is small
- Observations on measure and lowness for \(\Delta_ 2^ p\)
- On pseudorandomness and resource-bounded measure
- PP is as Hard as the Polynomial-Time Hierarchy
- Randomness vs time: Derandomization under a uniform assumption
- Relative to a random oracle, NP is not small
- Separating NP-completeness notions under strong hypotheses
- The Complexity and Distribution of Hard Problems
- The Density of Weakly Complete Problems under Adaptive Reductions
- The zero-one law holds for BPP
- Weak completeness in \(\text{E}\) and \(\text{E}_{2}\)
Cited in
(4)
This page was built for publication: The size of SPP
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q596117)