Kolmogorov characterizations of complexity classes

DOI10.1016/0304-3975(91)90282-7zbMath0727.68045OpenAlexW1989364208MaRDI QIDQ804291

Gerd Wechsung, Hemaspaandra, Lane A.

Publication date: 1991

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(91)90282-7

zbMATH Keywords

Kolmogorov complexitypolynomial hierarchy

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (1)

Ker-I Ko and the Study of Resource-Bounded Kolmogorov Complexity

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The strong exponential hierarchy collapses
• Probabilistic polynomial time is closed under parity reductions
• \(P^{NP[O(\log n)}\) and sparse turing-complete sets for NP]
• The complexity of optimization problems
• Complexity classes without machines: on complete languages for UP
• A note on sparse oracles for NP
• Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
• Relative complexity of checking and evaluating
• Complexity of Presburger arithmetic with fixed quantifier dimension
• Sparse sets in NP-P: EXPTIME versus NEXPTIME
• Computational Complexity of Probabilistic Turing Machines
• P-Printable Sets
• A Survey of Russian Approaches to Perebor (Brute-Force Searches) Algorithms
• On the power of parity polynomial time

This page was built for publication: Kolmogorov characterizations of complexity classes