Avoiding simplicity is complex

DOI10.1007/S00224-011-9334-7zbMATH Open1253.68186OpenAlexW2042851910MaRDI QIDQ693072FDOQ693072

Eric Allender, Holger Spakowski

Publication date: 7 December 2012

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-011-9334-7

Recommendations

• Avoiding simplicity is complex
• The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory
• Power from Random Strings
• scientific article; zbMATH DE number 1335898
• scientific article

zbMATH Keywords

complexity theoryhitting setsKolmogorov complexity\(\mathrm{KNt}\) complexity\(\mathrm{Kt}\) complexity

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Cites Work

• Computational Complexity
• A Pseudorandom Generator from any One-way Function
• Non-deterministic exponential time has two-prover interactive protocols
• Randomness conservation inequalities; information and independence in mathematical theories
• Some consequences of the existnce of pseudorandom generators
• Separating Nondeterministic Time Complexity Classes
• \(BPP\) has subexponential time simulations unless \(EXPTIME\) has publishable proofs
• Title not available (Why is that?)
• In search of an easy witness: Exponential time vs. probabilistic polynomial time.
• Algebraic methods for interactive proof systems
• IP = PSPACE
• Resource-bounded Kolmogorov complexity revisited
• The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory
• Sparse sets in NP-P: EXPTIME versus NEXPTIME
• Avoiding simplicity is complex
• Title not available (Why is that?)
• Power from Random Strings
• Polynomial-time compression
• Unconditional Lower Bounds against Advice
• Separating NE from Some Nonuniform Nondeterministic Complexity Classes

Cited In (7)

• Simplify or perish
• Gadgets and Anti-Gadgets Leading to a Complexity Dichotomy
• Closure and nonclosure properties of the classes of compressible and rankable sets
• Avoiding simplicity is complex
• Title not available (Why is that?)
• Simplicity Is the Point
• What Simplicity Is Not

This page was built for publication: Avoiding simplicity is complex

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q693072)