Collapsing and separating completeness notions under average-case and worst-case hypotheses (Q693053)
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: Collapsing and separating completeness notions under average-case and worst-case hypotheses |
scientific article; zbMATH DE number 6113697
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Collapsing and separating completeness notions under average-case and worst-case hypotheses |
scientific article; zbMATH DE number 6113697 |
Statements
Collapsing and separating completeness notions under average-case and worst-case hypotheses (English)
0 references
7 December 2012
0 references
computational complexity
0 references
NP-completeness
0 references
Turing completeness
0 references
length-increasing reductions
0 references
approximable sets
0 references
0.86010826
0 references
0.8536605
0 references
0.8513662
0 references
0.8513345
0 references
0.84976405
0 references
0.8474002
0 references
