A general minimal pair theorem is presented. This theorem yields as corollaries many results about minimal pairs in the polynomial-time context obtained previously by various authors. Furthermore, the new counterintuitive result is obtained that there exist arbitrarily complex minimal pairs. Also, the question whether minimal pairs in NP are low is investigated.
Recommendations
Cites work
- A low and a high hierarchy within NP
- 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
- Bounding minimal pairs
- scientific article; zbMATH DE number 3815631 (Why is no real title available?)
- Lower Bounds for Pairs of Recursively Enumerable Degrees
- Minimal pairs of polynomial degrees with subexponential complexity
- On the Structure of Polynomial Time Reducibility
- On the structure of sets in NP and other complexity classes
- Tally languages and complexity classes
Cited in
(6)- The p-T-degrees of the recursive sets: Lattice embeddings, extensions of embeddings and the two-quantifier theory
- Nondiamond theorems for polynomial time reducibility
- Minimal pairs and complete problems
- Structural properties of bounded relations with an application to NP optimization problems
- Forming all pairs in a minimal number of steps
- scientific article; zbMATH DE number 4037840 (Why is no real title available?)
This page was built for publication: Minimal pairs for P
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q795830)
