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


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


[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.