The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory
From MaRDI portal
Publication:619899
DOI10.1016/j.jcss.2010.06.004zbMath1235.68085OpenAlexW2028930979MaRDI QIDQ619899
Detlef Ronneburger, Sambuddha Roy, Michal Koucký, Eric W. Allender
Publication date: 18 January 2011
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jcss.2010.06.004
Related Items (18)
Minimum Circuit Size, Graph Isomorphism, and Related Problems ⋮ The minimum oracle circuit size problem ⋮ The complexity of Boolean formula minimization ⋮ Non-Black-Box Worst-Case to Average-Case Reductions Within \(\mathsf{NP}\) ⋮ The Complexity of Complexity ⋮ Ker-I Ko and the Study of Resource-Bounded Kolmogorov Complexity ⋮ Limits on the Computational Power of Random Strings ⋮ On parametric timed automata and one-counter machines ⋮ Avoiding simplicity is complex ⋮ Minimum Circuit Size, Graph Isomorphism, and Related Problems ⋮ Unnamed Item ⋮ The non-hardness of approximating circuit size ⋮ Unnamed Item ⋮ Vaughan Jones, Kolmogorov Complexity, and the New Complexity Landscape around Circuit Minimization ⋮ Unnamed Item ⋮ Randomness and Intractability in Kolmogorov Complexity ⋮ Circuit lower bounds from NP-hardness of MCSP under turing reductions ⋮ Algorithmic networks: central time to trigger expected emergent open-endedness
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The strong exponential hierarchy collapses
- A natural encoding scheme proved probabilistic polynomial complete
- Non-deterministic exponential time has two-prover interactive protocols
- Data structures for distributed counting
- Derandomizing Arthur-Merlin games using hitting sets
- AM\(_{\text{exp}}\nsubseteq (\text{NP} \cap \text{coNP})\)/poly
- Strong nondeterministic polynomial-time reducibilities
- Relativized alternation and space-bounded computation
- On uniform circuit complexity
- Symmetric space-bounded computation
- Probabilistic complexity classes and lowness
- PSPACE is provable by two provers in one round
- \(BPP\) has subexponential time simulations unless \(EXPTIME\) has publishable proofs
- Hardness vs randomness
- Upward separation for FewP and related classes
- On resource-bounded instance complexity
- Separating classes in the exponential-time hierarchy from classes in PH
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- Randomness vs time: Derandomization under a uniform assumption
- Breaking generalized Diffie-Hellman modulo a composite is no easier than factoring
- Some consequences of the existnce of pseudorandom generators
- New lowness results for ZPP\(^{\text{NP}}\) and other complexity classes.
- In search of an easy witness: Exponential time vs. probabilistic polynomial time.
- Uniform constant-depth threshold circuits for division and iterated multiplication.
- Pseudorandomness for approximate counting and sampling
- Self-reducibility
- On uniformity within \(NC^ 1\)
- Resource-Bounded Kolmogorov Complexity Revisited
- Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses
- Number-theoretic constructions of efficient pseudo-random functions
- Circuit minimization problem
- Circuit-size lower bounds and non-reducibility to sparse sets
- On the Complexity of Learning Minimum Time-Bounded Turing Machines
- Simple extractors for all min-entropies and a new pseudorandom generator
- Low-End Uniform Hardness versus Randomness Tradeoffs for AM
- Avoiding Simplicity Is Complex
- Undirected connectivity in log-space
- Minimizing Disjunctive Normal Form Formulas and $AC^0$ Circuits Given a Truth Table
- Randomness conservation inequalities; information and independence in mathematical theories
- Storing a Sparse Table with 0 (1) Worst Case Access Time
- A new general derandomization method
- Relativization of questions about log space computability
- A Pseudorandom Generator from any One-way Function
- An application of the translational method
- Algebraic methods for interactive proof systems
- IP = PSPACE
- A Survey of Russian Approaches to Perebor (Brute-Force Searches) Algorithms
- ON HELPING AND INTERACTIVE PROOF SYSTEMS
- Power from Random Strings
- Two-Tape Simulation of Multitape Turing Machines
- The complexity of theorem-proving procedures
- An introduction to Kolmogorov complexity and its applications
- Natural proofs
- Hardness of approximate two-level logic minimization and PAC learning with membership queries
This page was built for publication: The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory
