Exponential lower bounds for some NP-complete problems in a restricted linear decision tree model (Q1050255)
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: Exponential lower bounds for some NP-complete problems in a restricted linear decision tree model |
scientific article; zbMATH DE number 3809332
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Exponential lower bounds for some NP-complete problems in a restricted linear decision tree model |
scientific article; zbMATH DE number 3809332 |
Statements
Exponential lower bounds for some NP-complete problems in a restricted linear decision tree model (English)
0 references
1983
0 references
23, 181-192 (1983)
0 references
exponential lower bounds
0 references
restricted linear decision tree model
0 references
linear recognition problem
0 references
ternary comparisons
0 references
lower bounds on the number of comparisons
0 references
linear test functions
0 references
NP-completeness
0 references
