On resource-bounded instance complexity

DOI10.1016/0304-3975(95)00097-6zbMath0872.68044OpenAlexW1966098169MaRDI QIDQ1351945

Martin Kummer, Lance J. Fortnow

Publication date: 27 February 1997

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

Full work available at URL: https://doi.org/10.1016/0304-3975(95)00097-6

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (6)

Computational depth: Concept and applications ⋮ Resource-bounded kolmogorov complexity revisited ⋮ The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory ⋮ Generation Complexity Versus Distinction Complexity ⋮ On hard instances ⋮ Resource bounded symmetry of information revisited

Cites Work

• On one-one polynomial time equivalence relations
• On the notion of infinite pseudorandom sequences
• Polynomial terse sets
• On sparse sets in NP-P
• On reductions of NP sets to sparse sets
• Almost every set in exponential time is P-bi-immune
• Random strings make hard instances
• P-selective sets, tally languages, and the behavior of polynomial time reducibilities onNP
• Instance complexity
• Kolmogorov Complexity and Instance Complexity of Recursively Enumerable Sets
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: On resource-bounded instance complexity