Avoiding simplicity is complex

DOI10.1007/S00224-011-9334-7zbMath1253.68186OpenAlexW2042851910MaRDI QIDQ693072

Holger Spakowski, Eric W. 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

Kolmogorov complexitycomplexity theoryhitting sets\(\mathrm{KNt}\) complexity\(\mathrm{Kt}\) complexity

Mathematics Subject Classification ID

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

Related Items (1)

Closure and nonclosure properties of the classes of compressible and rankable sets

Cites Work

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

This page was built for publication: Avoiding simplicity is complex