Minimal pairs for P (Q795830)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Minimal pairs for P |
scientific article |
Statements
Minimal pairs for P (English)
0 references
1984
0 references
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.
0 references
polynomial reduction
0 references
P
0 references
general minimal pair theorem
0 references
NP
0 references
0 references
