On resource-bounded instance complexity
From MaRDI portal
Recommendations
Cites work
- scientific article; zbMATH DE number 3888913 (Why is no real title available?)
- scientific article; zbMATH DE number 46423 (Why is no real title available?)
- scientific article; zbMATH DE number 107774 (Why is no real title available?)
- scientific article; zbMATH DE number 192916 (Why is no real title available?)
- scientific article; zbMATH DE number 512802 (Why is no real title available?)
- scientific article; zbMATH DE number 4001485 (Why is no real title available?)
- Almost every set in exponential time is P-bi-immune
- Instance complexity
- Kolmogorov Complexity and Instance Complexity of Recursively Enumerable Sets
- On one-one polynomial time equivalence relations
- On reductions of NP sets to sparse sets
- On sparse sets in NP-P
- On the notion of infinite pseudorandom sequences
- P-selective sets, tally languages, and the behavior of polynomial time reducibilities onNP
- Polynomial terse sets
- Random strings make hard instances
Cited in
(10)- Kolmogorov Complexity and Instance Complexity of Recursively Enumerable Sets
- Resource bounds and subproblem independence
- Resource-bounded instance complexity
- Resource bounded symmetry of information revisited
- Resource-bounded Kolmogorov complexity revisited
- Generation Complexity Versus Distinction Complexity
- Computational depth: Concept and applications
- On hard instances
- The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory
- Instance complexity
This page was built for publication: On resource-bounded instance complexity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1351945)
