Kolmogorov characterizations of complexity classes
From MaRDI portal
Recommendations
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)