Kolmogorov characterizations of complexity classes

DOI10.1016/0304-3975(91)90282-7MaRDI QIDQ804291zbMATH OpenOpenAlexFDO

Authors Gerd Wechsung, Lane A. Hemaspaandra

Publication date 1991

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

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

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

zbMATH Keywords

polynomial hierarchyKolmogorov complexity

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 223336
• scientific article; zbMATH DE number 223337
• scientific article; zbMATH DE number 107775
• scientific article; zbMATH DE number 3885883
• Characterizations of some complexity classes between \(\Theta_2^{\mathrm{P}}\) and \(\Delta_2^{\mathrm{P}}\)

Cites work

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

Cited in

(5)

• Dimension Characterizations of Complexity Classes
• Ker-I Ko and the Study of Resource-Bounded Kolmogorov Complexity
• A note on the Kolmogorov data complexity and nonuniform logical definitions
• HIERARCHIES OF GENERALIZED KOLMOGOROV COMPLEXITIES AND NONENUMERABLE UNIVERSAL MEASURES COMPUTABLE IN THE LIMIT
• scientific article; zbMATH DE number 6741918 (Why is no real title available?)

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q804291)