Speedup for natural problems and noncomputability (Q620964)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Speedup for natural problems and noncomputability |
scientific article |
Statements
Speedup for natural problems and noncomputability (English)
0 references
2 February 2011
0 references
speedability
0 references
superpolynomial speedup
0 references
coNP-complete language
0 references
propositional proof system
0 references
optimal algorithm
0 references
0 references
