×
Ukkonen, Esko

Exponential lower bounds for some NP-complete problems in a restricted linear decision tree model. (English) Zbl 0512.90076

BIT 23, 181-192 (1983).
Page: −5 −4 −3 −2 −1 ±0 +1 +2 +3 +4 +5 Show Scanned Page
scan of Zbl 0512.90076

Cited in 3 Documents

MSC:

90C10 Integer programming
68Q25 Analysis of algorithms and problem complexity

Keywords:

23, 181-192 (1983); exponential lower bounds; restricted linear decision tree model; linear recognition problem; ternary comparisons; lower bounds on the number of comparisons; linear test functions; NP-completeness
Cite Review PDF
Full Text: DOI

References:

[1] D. Dobkin and R. Lipton,A lower bound of 1/2 n 2 on linear search programs for the knapsack problem, J. Comput. System. Sci. 16 (1978), 413–417 · Zbl 0397.68045 · doi:10.1016/0022-0000(78)90026-0
[2] D. P. Dobkin and R.J. Lipton,On the complexity of computations under varying sets of primitives. J. Comput. System Sci. 18 (1979), 86–91. · Zbl 0409.68023 · doi:10.1016/0022-0000(79)90054-0
[3] M. R. Garey and D. S. Johnson,Computers and Intractability. Freeman, San Francisco, 1979.
[4] R. M. Karp,Reducibility among combinatorial problems. In:Complexity of Computer Computations (R. E. Miller and J. W. Thatcher, eds.), Plenum Press, New York-London, 1972, pp. 85–103.
[5] M. O. Rabin,Proving simultaneous positivity of linear forms. J. Comput. System Sci. 6 (1972), 639–650. · Zbl 0274.68022 · doi:10.1016/S0022-0000(72)80034-5
[6] E. M. Reingold,Computing the maxima and the median. Proc. 12th Ann. Symp. on Switching and Automata Theory (1971), 216–218.
[7] M. Snir,Proving lower bounds for linear decision trees. In:Automata, Languages, and Programming, Eighth Colloquium, Acre, July 1981. Springer Lecture Notes in Computer Science 115 (1981), 305–315. · Zbl 0471.68027
[8] A. C. Yao,On the parallel computation for the knapsack problem. Proc. 13th Ann. ACM Symp. on Theory of Computing (1981), 123–127.
[9] A. C. Yao and R. L. Rivest,On the polyhedral decision problem. SIAM J. on Computing 9 (1980), 343–347. · Zbl 0447.68076 · doi:10.1137/0209028
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.