Avoiding simplicity is complex
From MaRDI portal
Publication:693072
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
Kolmogorov complexitycomplexity theoryhitting sets\(\mathrm{KNt}\) complexity\(\mathrm{Kt}\) complexity
Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items (1)
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