Notes on polynomial levelability (Q1119389)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Notes on polynomial levelability |
scientific article |
Statements
Notes on polynomial levelability (English)
0 references
1988
0 references
The author addresses the question whether certain types of approximation algorithms for intractable problems admit certain speed-up phenomena. It is shown that invertibly paddable sets as well complete sets for EXPTIME do have such speed-up properties.
0 references
polynomial levelability
0 references
approximation algorithms
0 references
