The size of SPP

DOI10.1016/J.TCS.2004.02.029zbMATH Open1068.68064OpenAlexW2053749801MaRDI QIDQ596117FDOQ596117

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

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

zbMATH Keywords

SPPResource-bounded measureWeak completeness

Mathematics Subject Classification ID

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

Cites Work

• Hardness vs randomness
• Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses
• On pseudorandomness and resource-bounded measure
• Almost everywhere high nonuniform complexity
• NP-hard sets are superterse unless NP is small
• Measure, Stochasticity, and the Density of Hard Languages
• 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
• Title not available (Why is that?)
• Title not available (Why is that?)
• Randomness vs time: Derandomization under a uniform assumption
• PP is as Hard as the Polynomial-Time Hierarchy
• Title not available (Why is that?)
• Graph Isomorphism is in SPP
• Separating NP-completeness notions under strong hypotheses
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Gap-definable counting classes
• The Complexity and Distribution of Hard Problems
• 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
• Relative to a random oracle, NP is not small
• MAX3SAT is exponentially hard to approximate if NP has positive dimension.
• Counting Classes are at Least as Hard as the Polynomial-Time Hierarchy
• Title not available (Why is that?)
• Fine Separation of Average-Time Complexity Classes
• Title not available (Why is that?)
• Title not available (Why is that?)
• The Density of Weakly Complete Problems under Adaptive Reductions

Cited In (4)

• Baire categories on small complexity classes and meager-comeager laws
• Title not available (Why is that?)
• All Maximum Size Two-Part Sperner Systems: In Short
• Martingale families and dimension in P

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)