The size of SPP

DOI10.1016/J.TCS.2004.02.029MaRDI QIDQ596117zbMATH OpenOpenAlexFDO

Authors John M. Hitchcock

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

zbMATH Keywords

SPPResource-bounded measureWeak completeness

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• scientific article; zbMATH DE number 2079071
• Size effect
• Dimension versus size
• scientific article; zbMATH DE number 3857775
• Size distributions reconsidered
• Size estimation of inclusion
• SIZE AND LOGIC
• Technical Note—On the Optimal Choice of Sizes
• Number Versus Size

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)

• Baire categories on small complexity classes and meager-comeager laws
• All Maximum Size Two-Part Sperner Systems: In Short
• Martingale families and dimension in P
• Nonuniform reductions and NP-completeness

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)