Notes on polynomial levelability (Q1119389)
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: Notes on polynomial levelability |
scientific article; zbMATH DE number 4098713
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Notes on polynomial levelability |
scientific article; zbMATH DE number 4098713 |
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
