Avoiding simplicity is complex

DOI10.1007/S00224-011-9334-7MaRDI QIDQ693072zbMATHOpenAlexFDO

Authors Holger Spakowski, Eric Allender

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

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)

Recommendations

• Avoiding simplicity is complex
• The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory
• Power from Random Strings
• Publication:4258589
• Publication:4023359

Cites work

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

Cited in

(8)

• scientific article; zbMATH DE number 5360956 (Why is no real title available?)
• Gadgets and Anti-Gadgets Leading to a Complexity Dichotomy
• Closure and nonclosure properties of the classes of compressible and rankable sets
• Simplicity Is the Point
• What Simplicity Is Not
• Avoiding simplicity is complex
• Large sets in \(\mathrm{AC}^{0}\) have many strings with low Kolmogorov complexity
• Simplify or perish

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)