The Complexity of Complexity
From MaRDI portal
Research exposition (monographs, survey articles) pertaining to computer science (68-02) Analysis of algorithms and problem complexity (68Q25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of computation (including implicit computational complexity) (03D15)
Cites work
- 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?)
- 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
- Investigations concerning the structure of complete sets
- Kolmogorov entropy in the context of computability theory
- Limitations of Hardness vs. Randomness under Uniform Reductions
- Limitations of efficient reducibility to the Kolmogorov random strings
- 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
- NL-printable sets and nondeterministic Kolmogorov complexity
- Natural proofs
- 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 NP-Completeness of the Minimum Circuit Size Problem.
- 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
- 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
- \(\text{S}_{2}^{\text{P}} \subseteq \text{ZPP}^{\text{NP}}\)
Cited in
(27)- One-way functions and pKt complexity
- Defying gravity and gadget numerosity: the complexity of the Hanano puzzle
- Complexity and the bulk volume, a New York time story
- Randomness and intractability in Kolmogorov complexity
- scientific article; zbMATH DE number 1996214 (Why is no real title available?)
- Circuit lower bounds from NP-hardness of MCSP under turing reductions
- scientific article; zbMATH DE number 1865706 (Why is no real title available?)
- Grammar of Complexity
- Gadgets and Anti-Gadgets Leading to a Complexity Dichotomy
- scientific article; zbMATH DE number 90342 (Why is no real title available?)
- The complexes of Peter Sellers
- On the complexity of circulations
- Five surprisingly simple complexities
- An efficient coding theorem via probabilistic representations and its applications
- Complexity with Rod
- Complexity and Fuzziness in 20th Century Science and Technology
- Vaughan Jones, Kolmogorov Complexity, and the New Complexity Landscape around Circuit Minimization
- NP-hardness of approximating meta-complexity: a cryptographic approach
- NP-hardness of approximating meta-complexity: a cryptographic approach
- On the complexity of automatic complexity
- Hardness magnification near state-of-the-art lower bounds
- A question of ``complexity
- Complexity and behind the horizon cut off
- Nonuniform reductions and NP-completeness
- The Complexity of Snake
- Nonuniform reductions and NP-completeness
- Simplicity via Complexity: Sandboxes, Reading Novalis
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)
