Minimal pairs for P (Q795830)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Minimal pairs for P |
scientific article; zbMATH DE number 3863184
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Minimal pairs for P |
scientific article; zbMATH DE number 3863184 |
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
