Exponential lower bounds for some NP-complete problems in a restricted linear decision tree model (Q1050255)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Exponential lower bounds for some NP-complete problems in a restricted linear decision tree model |
scientific article |
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
