The Complexity of Complexity
From MaRDI portal
Publication:2973719
DOI10.1007/978-3-319-50062-1_6zbMath1370.68114OpenAlexW2557365628MaRDI QIDQ2973719
Publication date: 4 April 2017
Published in: Computability and Complexity (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-319-50062-1_6
Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15) Research exposition (monographs, survey articles) pertaining to computer science (68-02) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items
Unnamed Item ⋮ Nonuniform reductions and NP-completeness ⋮ On the complexity of automatic complexity ⋮ Vaughan Jones, Kolmogorov Complexity, and the New Complexity Landscape around Circuit Minimization ⋮ Randomness and Intractability in Kolmogorov Complexity ⋮ Hardness magnification near state-of-the-art lower bounds ⋮ Circuit lower bounds from NP-hardness of MCSP under turing reductions
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Nondeterministic automatic complexity of overlap-free and almost square-free words
- The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory
- \(\text{S}_{2}^{\text{P}} \subseteq \text{ZPP}^{\text{NP}}\)
- A low and a high hierarchy within NP
- An excursion to the Kolmogorov random strings
- Limits on the computational power of random strings
- On the computational power of random strings
- NL-printable sets and nondeterministic Kolmogorov complexity
- Discrete logarithm and minimum circuit size
- What can be efficiently reduced to the Kolmogorov-random strings?
- Investigations Concerning the Structure of Complete Sets
- Reductions to the set of random strings: The resource-bounded case
- Curiouser and Curiouser: The Link between Incompressibility and Complexity
- Random strings and tt-degrees of Turing complete C.E. sets
- Zero Knowledge and Circuit Minimization
- On Characterizations of Randomized Computation Using Plain Kolmogorov Complexity
- The Minimum Oracle Circuit Size Problem.
- Algorithmic Randomness and Complexity
- Minimum Circuit Size, Graph Isomorphism, and Related Problems
- Circuit minimization problem
- Limitations of Hardness vs. Randomness under Uniform Reductions
- Minimizing Disjunctive Normal Form Formulas and $AC^0$ Circuits Given a Truth Table
- Randomness conservation inequalities; information and independence in mathematical theories
- Complexity Measures for Public-Key Cryptosystems
- On the hardness of approximating minimization problems
- On the complexity of random strings
- Communication Complexity
- Limitations of Efficient Reducibility to the Kolmogorov Random Strings
- On the complexity of communication complexity
- On the NP-Completeness of the Minimum Circuit Size Problem.
- Computational Complexity
- Power from Random Strings
- Natural proofs
- Reducing the complexity of reductions
- Kolmogorov entropy in the context of computability theory
