Feasibility testing for systems of real quadratic equations (Q2368126): Difference between revisions

Let \(G_ 1, G_ 2, \dots, G_ m\in \mathbb{R}[ X_ 1, X_ 2,\dots, X_ n]\) be quadratic forms and consider the problem of deciding whether there exists an \(x\in \mathbb{R}^ n\) such that \(x\neq 0\) and \(G_ 1(x)= G_ 2(x)= \dots= G_ m(x) =0\). The author describes a decision algorithm which, for a fixed number \(m\), uses a number of arithmetic operations bounded by a polynomial in \(n\). One of the main tools is to get some information on \(l:= \max(\{ F_ 1(x) F_ 2(x) \cdots F_ k(x)\mid x\in \mathbb{R}^ n\); \(\| x\| =1\})\) where \(F_ 1, F_ 2,\dots, F_ k\in \mathbb{R}[ X_ 1, X_ 2,\dots, X_ n]\) are positive definite quadratic forms. The author designs an algorithm to compute a univariate polynomial \(P\) of degree \(\leq (k+1) \cdot n^ k\) such that \(P(l)=0\); this algorithm uses, for fixed \(k\), a number of arithmetic operations which is bounded by a polynomial in \(n\) whose degree is linear in \(k^ 2\).