Document Zbl 0409.68023

On the complexity of computations under varying sets of primitives. (English) Zbl 0409.68023

J. Comput. Syst. Sci. 18, 86-91 (1979).

Page: −5 −4 −3 −2 −1 ±0 +1 +2 +3 +4 +5 Show Scanned Page
scan of Zbl 0409.68023

MSC:

68Q25	Analysis of algorithms and problem complexity
68R99	Discrete mathematics in relation to computer science
90B40	Search theory
90C10	Integer programming

Keywords:

Computational Complexity; Search Programm; Generalized Hyperplane; Search Problem; N-Dimensional Knapsack Problem

Cite Review PDF

Full Text: DOI

References:

[1]	Dobkin, D., A nonlinear lower bound on linear search tree programs for solving knapsack problems, J. Comput. System Sci., 13, 69-73 (1976) · Zbl 0338.68041
[2]	Dobkin, D.; Lipton, R. J., On some generalizations of binary search, (ACM Symposium on the Theory of Computing. ACM Symposium on the Theory of Computing, Seattle, Wash. (May 1974)) · Zbl 0361.68063
[3]	Dobkin, D.; Lipton, R. J., A lower bound of \(12n^2\) on linear search programs for the knapsack problem, J. Comput. System Sci., 16, 413-417 (1978) · Zbl 0397.68045
[4]	Grüinbaum, B., Convex Polytopes (1967), Interscience: Interscience New York · Zbl 0163.16603
[5]	Lefschetz, S., Algebraic Geometry (1953), Princeton Univ. Press: Princeton Univ. Press Princeton, N. J · Zbl 0052.37504
[6]	Rabin, M., Proving the simultaneous positivity of linear forms, J. Comput. System Sci., 13, 639-650 (1972) · Zbl 0274.68022
[7]	Reincold, E., Computing the maximum and the median, (12th Annual Symposium on Switching and Automata Theory (1971)), 216-218

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.