Minimal pairs and complete problems

DOI10.1016/0304-3975(94)90234-8zbMath0801.03031OpenAlexW1984801035MaRDI 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 pairNP-complete setsdeterministic exponential timeelementary recursive setoracle dependentpolynomial many-one reductions

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Other degrees and reducibilities in computability and recursion theory (03D30)

Related Items (1)

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

Cites Work

• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Minimal pairs and complete problems