Exponential lower bounds for some NP-complete problems in a restricted linear decision tree model
- 1 June 1983
- journal article
- research article
- Published by Springer Nature in BIT Numerical Mathematics
- Vol. 23 (2) , 181-192
- https://doi.org/10.1007/bf02218439
Abstract
No abstract availableKeywords
This publication has 8 references indexed in Scilit:
- On the parallel computation for the knapsack problemPublished by Association for Computing Machinery (ACM) ,1981
- Proving lower bounds for linear decision treesLecture Notes in Computer Science, 1981
- On the Polyhedral Decision ProblemSIAM Journal on Computing, 1980
- On the complexity of computations under varying sets of primitivesJournal of Computer and System Sciences, 1979
- A lower bound of 12n2 on linear search programs for the Knapsack problemJournal of Computer and System Sciences, 1978
- Proving simultaneous positivity of linear formsJournal of Computer and System Sciences, 1972
- Reducibility among Combinatorial ProblemsPublished by Springer Nature ,1972
- Computing the maximum and the medianPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1971