Resource-bounded kolmogorov complexity revisited
From MaRDI portal
Publication:5047163
DOI10.1007/BFb0023452zbMath1498.68129MaRDI QIDQ5047163
Harry Buhrman, Lance J. Fortnow
Publication date: 9 November 2022
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Related Items (3)
Computational depth: Concept and applications ⋮ Finite state complexity ⋮ Finite state incompressible infinite sequences
Cites Work
- Unnamed Item
- Unnamed Item
- Computing functions with parallel queries to NP
- NP is as easy as detecting unique solutions
- The complexity of optimization problems
- Polynomial-time compression
- Functions computable with limited access to NP
- On resource-bounded instance complexity
- Classes of bounded nondeterminism
- The complexity of promise problems with applications to public-key cryptography
- Structural analysis of the complexity of inverse functions
- The complexity of generating and checking proofs of membership
- Computing Solutions Uniquely Collapses the Polynomial Hierarchy
- The complexity of theorem-proving procedures
This page was built for publication: Resource-bounded kolmogorov complexity revisited
