Minimal pairs of polynomial degrees with subexponential complexity

DOI10.1016/0304-3975(76)90007-4zbMath0332.68040OpenAlexW1981375347MaRDI QIDQ1228203

Michael Machtey

Publication date: 1976

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

Full work available at URL: https://doi.org/10.1016/0304-3975(76)90007-4

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items

Minimal pairs and complete problems ⋮ Remarks on recursion versus diagonalization and exponentially difficult problems ⋮ On the structure of sets in NP and other complexity classes ⋮ Polynomial and abstract subrecursive classes ⋮ Minimal pairs for P

Cites Work

• The honest subrecursive classes are a lattice
• On the Structure of Polynomial Time Reducibility
• On the Computational Complexity of Algorithms
• Unnamed Item
• Unnamed Item