Proving simultaneous positivity of linear forms
From MaRDI portal
Publication:2265260
DOI10.1016/S0022-0000(72)80034-5zbMath0274.68022MaRDI QIDQ2265260
Publication date: 1972
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Analysis of algorithms and problem complexity (68Q25) Numerical mathematical programming methods (65K05) Mathematical programming (90C99)
Related Items
A note on Rabin's width of a complete proof, Selection problems via \(m\)-ary queries, On decision trees for orthants, A polynomial-time linear decision tree for the traveling salesman problem and other NP-complete problems, On selecting the k largest with median tests, Randomization and the computational power of analytic and algebraic decision trees, Subquadratic algorithms for algebraic 3SUM, Discrete extremal problems, Vapnik-Chervonenkis Dimension of Parallel Arithmetic Computations, The complexity of selection and ranking in X+Y and matrices with sorted columns, On hardly linearly provable systems, Comparisons between linear functions can help, On selecting the \(k\) largest with restricted quadratic queries, Spira's theorems on complete linear proofs of systems of linear inequalities, Test complexity of generic polynomials, A nonlinear lower bound on linear search tree programs for solving knapsack-problems, Relative complexity of checking and evaluating, Lower bounds on the worst-case complexity of some oracle algorithms, A lower bound of \({1\over 2}n^2\) on linear search programs for the knapsack problem, Lower bounds for arithmetic networks, On the complexity of computations under varying sets of primitives, Complete linear proofs of systems of linear inequalities, On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines, Exponential lower bounds for some NP-complete problems in a restricted linear decision tree model, Decision trees: Old and new results., On the decisional complexity of problems over the reals, A randomized algorithm for finding maximum with \(O((\log n)^2)\) polynomial tests
Cites Work
