Kolmogorov characterizations of complexity classes

DOI10.1016/0304-3975(91)90282-7zbMATH Open0727.68045OpenAlexW1989364208MaRDI QIDQ804291FDOQ804291

Gerd Wechsung, Lane A. Hemaspaandra

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

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)

Cites Work

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

Cited In (5)

• 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
• Title not available (Why is that?)
• Dimension Characterizations of Complexity Classes

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)