Dobkin, David P.; Lipton, Richard J. 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 Cited in 1 ReviewCited in 28 Documents 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 PDF BibTeX XML Cite \textit{D. P. Dobkin} and \textit{R. J. Lipton}, J. Comput. Syst. Sci. 18, 86--91 (1979; Zbl 0409.68023) Full Text: DOI OpenURL 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, () · 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 New York [5] Lefschetz, S., Algebraic geometry, (1953), 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, (), 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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.