The Complexity of Complexity
From MaRDI portal
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) Analysis of algorithms and problem complexity (68Q25)
Cites work
- \(\text{S}_{2}^{\text{P}} \subseteq \text{ZPP}^{\text{NP}}\)
- A low and a high hierarchy within NP
- Algorithmic randomness and complexity.
- An excursion to the Kolmogorov random strings
- Circuit minimization problem
- Communication Complexity
- Complexity Measures for Public-Key Cryptosystems
- Computational Complexity
- Curiouser and curiouser: the link between incompressibility and complexity
- Discrete logarithm and minimum circuit size
- scientific article; zbMATH DE number 4023249 (Why is no real title available?)
- scientific article; zbMATH DE number 3582190 (Why is no real title available?)
- scientific article; zbMATH DE number 1351078 (Why is no real title available?)
- scientific article; zbMATH DE number 1161568 (Why is no real title available?)
- scientific article; zbMATH DE number 1747450 (Why is no real title available?)
- Investigations concerning the structure of complete sets
- Kolmogorov entropy in the context of computability theory
- Limitations of efficient reducibility to the Kolmogorov random strings
- Limitations of Hardness vs. Randomness under Uniform Reductions
- Limits of minimum circuit size problem as oracle
- Limits on the computational power of random strings
- Minimizing Disjunctive Normal Form Formulas and AC^0 Circuits Given a Truth Table
- Minimum circuit size, graph isomorphism, and related problems
- Natural proofs
- NL-printable sets and nondeterministic Kolmogorov complexity
- Nondeterministic automatic complexity of overlap-free and almost square-free words
- On characterizations of randomized computation using plain Kolmogorov complexity
- On the (non) NP-hardness of computing circuit complexity
- On the complexity of communication complexity
- On the complexity of random strings
- On the computational power of random strings
- On the hardness of approximating minimization problems
- On the NP-Completeness of the Minimum Circuit Size Problem.
- Power from Random Strings
- Random strings and truth-table degrees of Turing complete c.e. sets
- Randomness conservation inequalities; information and independence in mathematical theories
- Reducing the complexity of reductions
- The Minimum Oracle Circuit Size Problem.
- The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory
- What can be efficiently reduced to the Kolmogorov-random strings?
- Zero knowledge and circuit minimization
Cited in
(28)- On the complexity of automatic complexity
- Complexity and behind the horizon cut off
- The complexes of Peter Sellers
- Five surprisingly simple complexities
- Nonuniform reductions and NP-completeness
- Complexity and the bulk volume, a New York time story
- A question of ``complexity
- Complexity with Rod
- Complexity and Fuzziness in 20th Century Science and Technology
- Nonuniform reductions and NP-completeness
- Vaughan Jones, Kolmogorov Complexity, and the New Complexity Landscape around Circuit Minimization
- On the complexity of circulations
- scientific article; zbMATH DE number 90342 (Why is no real title available?)
- scientific article; zbMATH DE number 1996214 (Why is no real title available?)
- Simplicity via Complexity: Sandboxes, Reading Novalis
- Grammar of Complexity
- scientific article; zbMATH DE number 1865706 (Why is no real title available?)
- 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
- Gadgets and Anti-Gadgets Leading to a Complexity Dichotomy
- The Complexity of Snake
- Defying gravity and gadget numerosity: the complexity of the Hanano puzzle
- NP-hardness of approximating meta-complexity: a cryptographic approach
- NP-hardness of approximating meta-complexity: a cryptographic approach
- One-way functions and pKt complexity
- An efficient coding theorem via probabilistic representations and its applications
- Kolmogorov complexity characterizes statistical zero knowledge
This page was built for publication: The Complexity of Complexity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2973719)
