Polynomial-Time Decidability of Semidefinite Programming Feasibility

Polynomial-Time Decidability of Semidefinite Programming Feasibility

Definitions and mathematical statement

Given rational symmetric matrices $A_0,A_1,\ldots,A_m\in{\mathbb{Q}}^{d\times d}$, semidefinite feasibility asks whether \[ \exists x\in{\mathbb{R}}^m,\qquad A_0+\sum_{i=1}^m x_iA_i\succeq0, \] where $B\succeq0$ means $v^TBv\ge0$ for every $v\in{\mathbb{R}}^d$. The input size is the total binary encoding length of the matrix dimensions and rational entries. The question asks for a deterministic polynomial-time decision algorithm in this bit model. No promise of strict feasibility, a positive separation margin, or bounded conditioning is supplied. Approximate feasibility within a tolerance can fail to distinguish exactly feasible instances from weakly infeasible ones and is not a substitute.

Formulation and concept references: [S1].

Short English statement

Can exact feasibility of every rational semidefinite program be decided in polynomial bit time, even without interior-point or conditioning promises?

Research attempt

Scope, process, and first gap.

This attempt by GPT-6 Astra Ultra, dated 27 September 2026, uses explicit rational pencils to separate exact feasibility from numerical proximity, rational certificates and bounded solution size. The input is the binary rational description. No strict-feasibility or conditioning promise is introduced. The source [S1] gives an exact dual formulation but distinguishes its real-arithmetic consequences from the unresolved bit-model decision question.

The first gap is a polynomial-bit-time decision procedure that handles singular feasible faces and weak infeasibility without assuming short rational solutions. The examples below disprove several stronger premises often used to bypass that gap. They do not prove that the decision problem requires superpolynomial time.

A zero diagonal entry forces a zero row.

For a positive semidefinite matrix $B$, if $B_{ii}=0$ then $B_{ij}=0$ for every $j$. To prove it, evaluate the quadratic form at $e_i+te_j$: \[ 0\le 2tB_{ij}+t^2B_{jj}. \] If $B_{ij}\ne0$, take $t$ of sufficiently small magnitude and opposite sign. The linear term dominates and makes the expression negative. This proves the claim without a nonsingularity assumption.

This elementary fact is a basic facial-reduction operation. It is exact: replacing a zero by a tiny positive tolerance changes what can be inferred about the off-diagonal entries.

An infeasible pencil arbitrarily close to the cone.

Consider the one-variable rational pencil \[ B(x)=\begin{pmatrix}0&1\\1&x\end{pmatrix}. \tag{269.1} \] Its zero diagonal and nonzero off-diagonal entry make it infeasible for every real $x$. Nevertheless, for every $\varepsilon>0$, \[ C_\varepsilon= \begin{pmatrix}\varepsilon&1\\1&1/\varepsilon\end{pmatrix} \succeq0,\qquad \|C_\varepsilon-B(1/\varepsilon)\|_{\mathrm F}=\varepsilon. \] Indeed $C_\varepsilon$ has positive diagonal and determinant zero. Hence the affine set has distance zero from the positive semidefinite cone despite being disjoint from it.

The smaller eigenvalue of $269.1$ is \[ \lambda_-(x)=\frac{x-\sqrt{x^2+4}}2 =-\frac{2}{x+\sqrt{x^2+4}} \quad(x>0). \] It tends to zero from below. Therefore a sequence of ever smaller eigenvalue violations is compatible with exact infeasibility. A numerical stopping rule accepting every matrix with violation below a positive threshold would eventually accept this infeasible instance.

There is also no ordinary strict separating certificate of the simplest dual form. Such a certificate would be $Y\succeq0$ with $\langle A_1,Y\rangle=0$ and $\langle A_0,Y\rangle<0$. Here the first equation says $Y_{22}=0$, so the zero-row lemma gives $Y_{12}=0$, and the second inner product is zero rather than negative. The calculation explains why an exact extended dual is more than the usual separating hyperplane.

A feasible rational pencil with no rational feasible point.

Take the block diagonal pencil \[ A(x)= \begin{pmatrix}x&2\\2&2x\end{pmatrix} \ \oplus\ \begin{pmatrix}1&x\\x&2\end{pmatrix}. \tag{269.2} \] The first block is positive semidefinite exactly when $x\ge0$ and $2x^2-4\ge0$, that is, $x\ge\sqrt2$. The second is positive semidefinite exactly when $2-x^2\ge0$. Their intersection is \[ \{x:A(x)\succeq0\}=\{\sqrt2\}. \] Thus rational input does not imply existence of a rational feasible vector. The pencil is feasible over the reals and has no rational solution.

A search over rational vectors will never find a witness here, regardless of how many bits are allowed. This does not preclude algebraic certificates or other decision methods: $\sqrt2$ has a short exact algebraic description. It refutes only a purported universal argument based on rational feasible points.

The singularity is essential to this particular phenomenon. If a rational pencil is strictly feasible at some real vector, openness of positive definiteness and density of rational vectors give a rational strictly feasible point nearby. That observation still gives no uniform polynomial bound on its bit length.

Feasible vectors can require very large ordinary encodings.

For variables $x_1,\ldots,x_t$, impose the scalar block $x_1-2\ge0$ and the blocks \[ \begin{pmatrix}x_{i+1}&x_i\\x_i&1\end{pmatrix}\succeq0 \qquad(1\le i<t). \tag{269.3} \] All coefficients are small integers. Each block is equivalent to $x_{i+1}\ge x_i^2$, so every feasible vector satisfies \[ x_t\ge 2^{\,2^{t-1}}. \] Equality throughout gives a feasible integer vector, proving the instance is nonempty.

Any explicit binary rational encoding of such an $x_t$ needs at least $2^{t-1}+1$ bits in its numerator when written with positive integer denominator. The entire pencil has dimension $2t-1$ and polynomial encoding length in $t$, even counting all zero entries. Thus ordinary coordinate witnesses need not have polynomial bit length in the explicit input size.

The example even admits strictly feasible points by making every inequality strict. It shows why mere nonemptiness of the interior is not a quantitative boundedness promise. It does not rule out a short symbolic description such as repeated squaring, and the decision answer itself is just one bit. A large-witness argument alone is therefore not a decision lower bound.

An exact finite-algebraic formulation.

A real symmetric matrix is positive semidefinite if and only if it is a Gram matrix. Consequently the original question is equivalent to \[ \exists x\in\mathbb R^m,\ \exists R\in\mathbb R^{d\times d}: \quad A_0+\sum_i x_iA_i=RR^{\mathsf T}. \tag{269.4} \] The forward direction uses an orthogonal diagonalization and nonnegative square roots of eigenvalues. The reverse direction follows from $v^{\mathsf T}RR^{\mathsf T}v=\|R^{\mathsf T}v\|^2\ge0$. This is a polynomial-size system of rational polynomial equations of degree at most two.

Real quantifier-elimination algorithms [E1] therefore give a total exact decision procedure. This is an established algebraic decidability tool, not a polynomial-time bound: the number of variables grows with the input. Replacing a universal quadratic-form condition by $269.4$ does not make general real polynomial feasibility easy.

For comparison, when every input matrix is diagonal, the condition reduces to finitely many rational linear inequalities. That is ordinary linear programming, for which polynomial bit-time feasibility is established. The off-diagonal constraints in $269.1$--$269.3$ are exactly what makes those examples escape this linear subclass.

A valid facial reduction when the certificate is supplied.

Suppose a known matrix $Y\succeq0$ has \[ \langle Y,A_0\rangle=\langle Y,A_i\rangle=0 \quad\text{for all }i. \] For any feasible $A(x)$, the matrix $Y^{1/2}A(x)Y^{1/2}$ is positive semidefinite with trace zero. All its eigenvalues are nonnegative and sum to zero, so it vanishes. Equivalently, $A(x)^{1/2}Y^{1/2}=0$, and hence \[ \operatorname{range} A(x)\subseteq\ker Y. \] Thus the feasible matrices lie in a smaller face of the cone. If an exact basis of $\ker Y$ is available, impose that the complementary rows and columns vanish and restrict the remaining positive semidefinite block to that subspace.

This implication is sound and includes the zero-diagonal lemma as a simple instance. It does not explain how to discover all needed exposing matrices in polynomial bit time, or how to encode their entries uniformly. The source's polynomial-size extended formulation must not be confused with a guarantee that all relevant real solutions have short rational coordinates.

Verification and outcome.

The local checks verify the two-by-two principal minors and the exact repeated-squaring construction. Rational $\varepsilon$ values demonstrate zero distance in $269.1$ with certified positive semidefinite comparison matrices. The irrational singleton is proved symbolically, not inferred from a small numerical residual.

UNRESOLVED. Exact decidability, elementary subclasses and the stated obstruction examples are established. The remaining step is a deterministic polynomial bit-time algorithm for every rational pencil, including weakly infeasible and singular feasible cases. Neither numerical tolerance, a naive rational search nor the size of an extended dual resolves that step.

Sources

• S1 A combinatorial approach to Ramana's exact dual for semidefinite programming $2025$. https://arxiv.org/html/2510.07271. Formulation source.
• E1 Katherine Kosaian, Yong Kiam Tan, and André Platzer, A First Complete Algorithm for Real Quantifier Elimination in Isabelle/HOL, arXiv:2209.10978 $2022$. https://arxiv.org/abs/2209.10978. Primary source establishing a complete real quantifier-elimination algorithm; no polynomial-time guarantee for the SDP target is inferred.