Minimal pairs and complete problems

DOI10.1016/0304-3975(94)90234-8zbMath0801.03031MaRDI QIDQ1334663

Robert I. Soare, Ambos-Spies, Klaus, Homer, Steven

Publication date: 25 September 1994

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

Full work available at URL: https://doi.org/10.1016/0304-3975(94)90234-8

zbMATH Keywords

minimal pair; NP-complete sets; deterministic exponential time; elementary recursive set; oracle dependent; polynomial many-one reductions

Mathematics Subject Classification ID

03D15: Complexity of computation (including implicit computational complexity)

03D30: Other degrees and reducibilities in computability and recursion theory

Related Items

Decidability of the two-quantifier theory of the recursively enumerable weak truth-table degrees and other distributive upper semi-lattices

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Oracle-dependent properties of the lattice of NP sets
• Minimal pairs for P
• A note on structure and looking back applied to the relative complexity of computable functions
• A uniform approach to obtain diagonal sets in complexity classes
• Nondiamond theorems for polynomial time reducibility
• Minimal pairs of polynomial degrees with subexponential complexity
• An Inhomogeneity in the Structure of Karp Degrees
• On the Structure of Polynomial Time Reducibility
• Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question