Semi-Algebraic Proof Systems for QBF Thanks: An extended abstract of this article has appeared in proceedings of SAT’25 [ BBK+25 ] . Olaf Beyersdorff and Kaspar Kasche were supported by Carl-Zeiss Foundation. Olaf Beyersdorff was additionally supported by DFG grant BE 4209/3-1. Ilario Bonacina was funded by the AEI with the grant number PID2022-138506NB-C22. Meena Mahajan was partially supported by the J. C. Bose Fellowship of SERB, ANRF. Olaf Beyersdorff, Ilario Bonacina, Kaspar Kasche, Meena Mahajan, Luc Nicolas Spachmann Abstract We introduce new semi-algebraic proof systems for Quantified Boolean Formulas (QBF) analogous to the propositional systems Nullstellensatz, Sherali-Adams and Sum-of-Squares. We transfer to this setting techniques both from the QBF literature (strategy extraction) and from propositional proof complexity (size-degree relations and pseudo-expectation). We obtain a number of strong QBF lower bounds and separations between these systems, even when disregarding propositional hardness. 1 Introduction Two key results in algebraic and semi-algebraic geometry are the Nullstellensatz and the Positivstellensatz. The first can be seen as an algebraic identity certifying that a set of polynomial equations is unsatisfiable while the second as an algebraic identity certifying that a system of polynomial inequalities is unsatisfiable. In other words, both the Nullstellensatz and the Positivstellensatz naturally give rise to proof systems and in recent years intense research was performed on the proof complexity of such systems. In particular, the proof system Sum-of-Squares , a special case of Positivstellensatz, starting from [ BBH+12 ] , has received a lot of attention for its connection with algorithms based on hierarchies of SDP relaxations (see for instance [ Las01 , OZ13 ] ). For similar reasons, the even more restrictive Sherali-Adams proof system has been investigated, named after its connection with the Sherali-Adams hierarchy of linear programming since its original definition (see for instance [ SA90 , DM13 ] ). In this work, we devise a simple and natural way to extend the proof systems Nullstellensatz ( \mathsf{NS} ), Sum-of-Squares ( \mathsf{SOS} ) and Sherali-Adams ( \mathsf{SA} ) from the context of propositional existentially quantified variables to existentially and universally quantified variables. In other words, we show how to define proof systems for quantified Boolean formulas (QBF) inspired by the propositional proof systems above. The study of propositional and QBF proof systems is motivated both by theoretical reasons and also by connections to SAT and QBF solving [ BN21 , BJLS21 , Bey22 ] . While for SAT-solvers conflict-driven clause learning (CDCL) is the ruling paradigm, which by the seminal work of [ AFT11 , PD11 ] is essentially equivalent to the propositional proof system Resolution ( Res ), there are several competing approaches in QBF, with CDCL-based [ ZM02 ] and expansion -based solving [ JM15 ] among the main paradigms. To model the strength of QBF-solvers several (often incomparable) QBF proof systems have been introduced and analysed [ ELW13 , JM15 , BB23 ] . Of most relevance to this work is QU-Resolution ( \mathsf{QU}\text{-}\textsf{Res} ) [ KKF95 , VG12 ] . \mathsf{QU}\text{-}\textsf{Res} adds to propositional Resolution the \forall -reduction rule that allows to eliminate universal variables from clauses. In [ BBCP20 ] it has been shown that this approach of augmenting a propositional proof system by a \forall -reduction rule taking care of universal quantifiers also works for other common inference-based proof systems such as various Frege systems [ CR79 , BBCP20 ] , Cutting Planes [ CCT87 , BCMS18 ] —a proof system modelling geometric reasoning related to Chvátal-Gomory cuts— and Polynomial Calculus [ CEI96 , BHKS24 ] , modelling algebraic reasoning related to Gröbner bases computations. A common feature of all the propositional proof systems above is that they are inference -based, unlike the static systems \mathsf{NS} / \mathsf{SA} / \mathsf{SOS} where a proof is just an algebraic identity of some specific form depending on the system at hand. This has posed quite some problems to adapt such systems to the QBF setting, and it was not clear at all whether an approach similar to a \forall -reduction rule was even viable. Recently there has been a suggestion to define QBF analogues of \mathsf{NS} based on \forall -expansion [ CCKS23 ] , but these differ considerably from our approach here and the \forall -reduction paradigm discussed above. We show that an approach similar to a \forall -reduction rule does allow to define QBF versions of \mathsf{NS} / \mathsf{SA} / \mathsf{SOS} , which we call \mathsf{Q}\text{-}\mathsf{NS} / \mathsf{Q}\text{-}\mathsf{SA} / \mathsf{Q}\text{-}\mathsf{SOS} respectively. We argue that our definitions are quite natural: they add to the algebraic equations of \mathsf{NS} / \mathsf{SA} / \mathsf{SOS} simple polynomials that strongly resemble \forall -reduction and meet the same technical condition on variable dependence. We begin the systematic study of these QBF proof systems in terms of lower and upper bounds, strategy extraction, and simulations. Concerning the latter, fig. 1(a) recalls the relations between propositional \mathsf{NS} / \mathsf{SA} / \mathsf{SOS} and further propositional proof systems such as Resolution ( Res ) and Polynomial Calculus ( \mathsf{PC} ). In fig. 1(b) , we depict our results on the new QBF systems \mathsf{Q}\text{-}\mathsf{NS} / \mathsf{Q}\text{-}\mathsf{SA} / \mathsf{Q}\text{-}\mathsf{SOS} and how they relate to \mathsf{QU}\text{-}\textsf{Res} and \mathsf{Q}\text{-}\mathsf{PC} . The figures are virtually identical: what changes is that proofs of the simulations, although mimicking those in the propositional setting, require extra care. fig. 1(c) depicts the simulation order when we factor out the propositional complexity and consider genuine QBF hardness stemming from quantifier alternations – a framework that has become standard in QBF proof complexity (cf. [ BHP20 , Che17 ] for background). We call the ‘genuine’ size measure qsize, which only counts monomial size in the new \forall -reduction polynomials. Lower bounds on qsize are tighter and trivially imply lower bounds on the traditional size measure that counts all monomials. Hence, lower bounds and separations in qsize are harder to obtain. In fact, \mathsf{Q}\text{-}\mathsf{SA} and \mathsf{Q}\text{-}\mathsf{SOS} become equivalent w.r.t. qsize while they are separated w.r.t. size. The fact that the systems we define fit so nicely into the lattice of QBF proof systems using the \forall -reduction approach suggests that the definitions we give are natural analogues of \forall -reduction in this context. The analogy with the \forall -reduction rule of \mathsf{QU}\text{-}\textsf{Res} gets even clearer when using the language of weighted clauses and Resolution to describe \mathsf{NS} and \mathsf{SA} [ BBL24 ] . For simplicity, we describe \mathsf{Q}\text{-}\mathsf{NS} and \mathsf{Q}\text{-}\mathsf{SA} first using the usual algebraic language, and in Section 6 we describe \mathsf{Q}\text{-}\mathsf{SA} also in the language of weighted clauses. \mathsf{NS} Res \mathsf{SA} \mathsf{PC} \mathsf{SOS} (trivial) [ ALN16 ] [ DMR09 ] PHP (trivial) [ Ber18 ] (a) propositional systems \mathsf{Q}\text{-}\mathsf{NS} \mathsf{QU}\text{-}\textsf{Res} \mathsf{Q}\text{-}\mathsf{SA} \mathsf{Q}\text{-}\mathsf{PC} \mathsf{Q}\text{-}\mathsf{SOS} (trivial) Thm. 7.1 [ ALN16 ] Thm. 7.3 PHP [ BBH19 ] Thm. 7.4 Thm. 7.5 (b) QBF systems p-simulations w.r.t. \size \mathsf{Q}\text{-}\mathsf{NS} \mathsf{QU}\text{-}\textsf{Res} \mathsf{Q}\text{-}\mathsf{SA} \mathsf{Q}\text{-}\mathsf{PC} \mathsf{Q}\text{-}\mathsf{SOS} Q-ExactMaj [ BBH19 ] Thm. 7.4 Q-Maj Thm. 7.5 Thm. 7.1 Thm. 7.2 (c) QBF systems p-simulations w.r.t. \qsize Figure 1 : Simulations and separations between algebraic proof systems in the propositional and the QBF setting. By P\rightarrow Q we indicate that proof system P polynomially simulates Q , while P\ {\color[rgb]{0.5,0.5,0.5}\dashrightarrow}\ Q means that the proof system P does not polynomially simulate Q . We omit polynomial (non-)simulations implied by those displayed. For lower and upper bounds we develop and adapt techniques that originate both from propositional and QBF proof complexity. Regarding the transfer of propositional techniques, we show how to lift common techniques for \mathsf{SOS} from the propositional setting to \mathsf{Q}\text{-}\mathsf{SOS} : we establish a size-degree relation analogous to the propositional one [ AH19 ] , and show how to adapt the notion of pseudo-expectation, the prime lower-bound method for semi-algebraic systems [ FKP19 ] to the QBF setting. Both adaptations require interesting modifications and do not just replicate the propositional techniques (see 3.12 and 5.1 with the discussion thereafter). We use pseudo-expectations to show an exponential lower bound for \mathsf{Q}\text{-}\mathsf{SOS} for the Equality QBFs [ BBH18 ] with respect to the tighter qsize measure ( 5.3 ). Regarding QBF techniques, we develop strategy extraction for \mathsf{Q}\text{-}\mathsf{SOS} . Strategy extraction has become the predominant technique to analyse QBF proof systems (see [ BCJ19 , BBCP20 , BBH19 ] for instance) and is also of tremendous practical importance for QBF solving and verification [ BJLS21 , ELW13 , BJ12 ] . Specifically, we show that \mathsf{Q}\text{-}\mathsf{SOS} allows strategy extraction by polynomial threshold functions and develop a new score game interpretation. Interestingly, this score game allows to characterise genuine proof size in \mathsf{Q}\text{-}\mathsf{SOS} and \mathsf{Q}\text{-}\mathsf{NS} (Theorem 3.7 ). We also use it to elegantly show completeness of the new systems and a linear upper bound for the Q-Majority QBFs, which are known to be hard for \mathsf{Q}\text{-}\mathsf{PC} [ BHKS24 ] , yielding the separation depicted in fig. 1(c) . Structure of the paper. Section 2 contains preliminaries and notation. Section 3 defines our new semi-algebraic QBF systems and shows their soundness and completeness together with the size-degree relation for \mathsf{Q}\text{-}\mathsf{SOS} . Section 4 contains the strategy extraction for \mathsf{Q}\text{-}\mathsf{SOS} and some consequences. In Section 5 we develop the lower bound technique of pseudo-expectations for \mathsf{Q}\text{-}\mathsf{SOS} and show an exponential lower bound. Section 6 shows a lifted weighted resolution to QBF and its equivalence to \mathsf{Q}\text{-}\mathsf{SA} . In Section 7 we compare the QBF systems via p-simulations. We conclude in Section 8 with some open problems. 2 Preliminaries QBF preliminaries. We consider Quantified Boolean Formulas (QBF) of the form \mathcal{Q}.\varphi , where \varphi is a CNF formula and \mathcal{Q} is the quantifier prefix. Both the variables of \varphi and the variables of \mathcal{Q} range over a set of Boolean variables V . Let \mathrm{vars}_{\forall}(\mathcal{Q}) (resp. \mathrm{vars}_{\exists}(\mathcal{Q}) ) be the set of universally (resp. existentially) quantified variables in \mathcal{Q} . The evaluation of a QBF formula \mathcal{Q}.\varphi can be seen as a game (the evaluation game) between two players: the existential \exists -player and the universal \forall -player, where the \exists -player’s goal is to satisfy the formula \varphi and the \forall -player’s goal is to falsify it. The players take turns according to the order of the quantifiers in \mathcal{Q} . We call this game the evaluation game to distinguish it from a new game, the score game, which we introduce in Section 3.1 . A very well-studied QBF proof system is \mathsf{QU}\text{-}\textsf{Res} [ BWJ14 , KKF95 , VG12 ] , which can be seen as a natural extension of the propositional proof system Resolution [ Bla37 , Rob65 ] to the QBF setting. The QBF proof system \mathsf{QU}\text{-}\textsf{Res} refutes a false QBF \mathcal{Q}.\varphi inferring the empty clause \bot from the clauses in \varphi using the resolution rule \frac{C\lor v\hskip 8.19447ptD\lor\lnot v}{C\lor D} , but also using a \forall -reduction rule \frac{C\lor u}{C} , where all the variables in C must be on the left of u in \mathcal{Q} . The size of a \mathsf{QU}\text{-}\textsf{Res} refutation \pi ( \size(\pi) ) is the number of applications of rules in \pi , while Q-size ( \qsize(\pi) ) is the number of applications of the \forall -reduction rule. Algebraic proof systems. Given a set of Boolean variables V , let \overline{V} be the set of new formal variables \overline{v} for v\in V . We consider polynomials with rational coefficients and variables in V\cup\overline{V} , i.e. polynomials in the ring \mathbb{Q}[V\cup\overline{V}] . Given a polynomial p and an assignment \alpha of its variables, we denote with \left.{p}\right|_{\alpha} the evaluation of p in \alpha . In this work we encode clauses and CNF formulas into polynomials using the so-called twin-variables encoding . A clause C=\bigvee_{v\in P}v\lor\bigvee_{v\in N}\lnot v is encoded as the set of polynomials \enc(C)=\left\{\prod_{v\in P}\overline{v}\prod_{v\in N}v\right\}\cup\{v^{2}-v,\ v+\overline{v}-1:v\in P\cup N\}\ . A CNF \varphi=\bigwedge_{j=1}^{m}C_{j} is encoded as a set of polynomials \enc(\varphi)=\bigcup_{j=1}^{m}\enc(C_{j}) . The formula \varphi is satisfiable if and only if the set of polynomial equalities \{p=0:p\in\enc(\varphi)\} is satisfiable. Fact 2.1 . Given a polynomial r\in\mathbb{Q}[V\cup\overline{V}] , if r evaluates to 0 over every Boolean assignment satisfying \varphi (and setting v+\overline{v} to 1 ), then r is in the ideal generated by \enc(\varphi) , i.e. there are polynomials q_{p} such that r=\sum_{p\in\enc(\varphi)}q_{p}p . A refutation of an unsatisfiable CNF \varphi in variables V in the system Nullstellensatz, \mathsf{NS} , (resp. Sherali-Adams, \mathsf{SA} , or Sum-of-Squares, \mathsf{SOS} ) is an algebraic identity \pi of the form \sum_{p\in\enc(\varphi)}q_{p}p+q+1=0\ , (1) where all the polynomials q_{p} , q are in \mathbb{Q}[V\cup\overline{V}] , and for \mathsf{NS} q is identically 0 (resp. for \mathsf{SA} q is a polynomial with non-negative coefficients, and for \mathsf{SOS} q=\sum_{s\in S}s^{2} , that is q is a sum of squares). The size of the \mathsf{NS}/\mathsf{SA}/\mathsf{SOS} refutation \pi , \size(\pi) , is the number of monomials (counted with repetition) in q_{p} and q . The degree of \pi , \deg(\pi) , is the maximum degree of any of the polynomials q_{p}p , and q . Remark 2.2 (On variations of \mathsf{NS} , \mathsf{SA} and \mathsf{SOS} ) . The proof system \mathsf{NS} has been considered also for polynomials over arbitrary fields [ BGIP01 ] . In this paper we focus only on polynomials with rational coefficients. The proof systems \mathsf{NS} , \mathsf{SA} and \mathsf{SOS} have been also studied using a different encoding of CNF formulas: the encoding \enc^{\prime}(C) , which is the same as \enc(C) but with each \bar{v} variable substituted by 1-v . The systems \mathsf{NS} , \mathsf{SA} and \mathsf{SOS} under the \enc^{\prime} encoding are exponentially weaker than the corresponding system under the encoding \enc [ dRLNS21 ] . In this paper we focus only on polynomials using the encoding \enc . The proof system \mathsf{SOS} has also been studied recently on Boolean variables representing the Boolean values as \pm 1 instead of 0/1 [ Sok20 ] , i.e. using instead of the polynomials v^{2}-v the polynomials v^{2}-1 . In this paper we focus only on polynomials using 0/1 -valued variables. Another well-studied algebraic propositional proof system is Polynomial Calculus ( \mathsf{PC} ) [ CEI96 ] . A Polynomial Calculus (over \mathbb{Q} ) refutation of the set of polynomials \enc(\varphi) , for an unsatisfiable CNF formula \varphi , is a sequence of polynomials showing that 1 can be derived from \enc(\varphi) using the inference rules \frac{p\hskip 8.19447ptq}{p+q} for polynomials p,q , and \frac{p}{vp} where v is a variable or v\in\mathbb{Q} . The degree and (monomial) size of the refutation are respectively the largest degree of a polynomial in it and the number of monomials in it (counted with multiplicity). In [ BBCP20 , BHKS24 ] , the authors showed how to extend the proof system \mathsf{PC} to the QBF context. This resulted in QBF proof system Q-Polynomial Calculus ( \mathsf{Q}\text{-}\mathsf{PC} ). \mathsf{Q}\text{-}\mathsf{PC} refutes a QBF \mathcal{Q}.\varphi analogously to the system \mathsf{PC} , i.e. showing that the polynomial 1 can be derived from the polynomials in \enc(\varphi) using the inference rules \frac{p\hskip 8.19447ptq}{p+q} for polynomials p,q , and \frac{p}{vp} where v is a variable or v\in\mathbb{Q} , but also using a \forall -reduction rule \frac{p}{\left.{p}\right|_{u=b}} , for b\in\{0,1\} where all the variables in p distinct from u must be left of u in \mathcal{Q} . The \size of a \mathsf{Q}\text{-}\mathsf{PC} refutation is the number of monomials in the refutation (counted with repetition), while the \qsize is the number of monomials in the polynomials involved in the \forall -reduction steps (again counted with repetition). The reason to study \qsize and not just \size is to factor out the propositional hardness of the principles and focus on genuine QBF hardness (cf. [ BHP20 , Che17 ] ). 3 Algebraic systems for QBFs We introduce new QBF proof systems inspired by propositional \mathsf{NS}/\mathsf{SA}/\mathsf{SOS} . We call them \mathsf{Q}\text{-}\mathsf{NS}/\mathsf{Q}\text{-}\mathsf{SA}/\mathsf{Q}\text{-}\mathsf{SOS} . As their propositional counterparts they are static proof systems: a refutation of a false QBF \mathcal{Q}.\varphi over variables V in Q-Nullstellensatz, \mathsf{Q}\text{-}\mathsf{NS} , (resp. Q-Sherali-Adams, \mathsf{Q}\text{-}\mathsf{SA} , and Q-Sum-of-Squares, \mathsf{Q}\text{-}\mathsf{SOS} ) is an algebraic identity \pi of the form \sum_{p\in\enc(\varphi)}q_{p}p+\sum_{u\in\mathrm{vars}_{\forall}(\mathcal{Q})}q_{u}(1-2u)+q+1=0\ , (2) where all the polynomials q_{p} , q_{u} q are in \mathbb{Q}[V\cup\overline{V}] , the variables in q_{u} are all quantified before u in \mathcal{Q} (i.e. on the left of u ), and for \mathsf{Q}\text{-}\mathsf{NS} q is identically 0 (resp. for \mathsf{Q}\text{-}\mathsf{SA} q is a polynomial with non-negative coefficients, and for \mathsf{Q}\text{-}\mathsf{SOS} q=\sum_{s\in S}s^{2} , that is q is a sum of squares). We call the expression in eq. ( 2 ) a \mathsf{Q}\text{-}\mathsf{NS} -refutation of \mathcal{Q}.\varphi (resp. \mathsf{Q}\text{-}\mathsf{SA} -refutation/ \mathsf{Q}\text{-}\mathsf{SOS} -refutation). Definition 3.1 (size, degree, \qsize and \qdeg ) . The size of a \mathsf{Q}\text{-}\mathsf{NS}/\mathsf{Q}\text{-}\mathsf{SA}/\mathsf{Q}\text{-}\mathsf{SOS} refutation \pi ( \size(\pi) ) is the number of monomials (counted with repetition) in q_{p} , q_{u} and q . The degree of \pi ( \deg(\pi) ) is the maximum degree of any of the polynomials q_{p}p , q_{u}(1-2u) , and q . The Q-size of \pi ( \qsize(\pi) ) is defined analogously to the \size but accounts only for the monomials in the polynomials q_{u} . The existential Q-degree of \pi ( \qdeg(\pi) ) is the maximum existential degree of any q_{u} , where the existential degree is the highest number of existentially quantified variables in any monomial. The definitions of size and degree for \mathsf{Q}\text{-}\mathsf{NS}/\mathsf{Q}\text{-}\mathsf{SA}/\mathsf{Q}\text{-}\mathsf{SOS} are completely analogous to the definitions in the propositional setting, while Q-size and Q-degree factor out propositional hardness and therefore give measures more appropriate to study principles where the hardness stems from quantification. The definition of Q-size also aligns with genuine QBF hardness measures defined in [ BHP20 ] and analysed e.g. in [ BBMP23 , BHKS24 ] for QU-Resolution and \mathsf{Q}\text{-}\mathsf{PC} , where only universal reduction steps are counted. In a sense, the polynomial q_{u} in ( 2 ) can be understood as a universal reduction step on u . In particular, on QBFs without universal variables, \mathsf{Q}\text{-}\mathsf{NS}/\mathsf{Q}\text{-}\mathsf{SA}/\mathsf{Q}\text{-}\mathsf{SOS} are equivalent to their propositional counterparts \mathsf{NS}/\mathsf{SA}/\mathsf{SOS} . Any lower bound on Q-size immediately implies the same lower bound on size. The reason to consider the existential Q-degree is a connection between Q-size and existential Q-degree similar to the inequality between size and width in resolution [ BBMP23 ] (see Section 3.3 ). As a first result we prove that \mathsf{Q}\text{-}\mathsf{NS} , \mathsf{Q}\text{-}\mathsf{SA} , \mathsf{Q}\text{-}\mathsf{SOS} are sound QBF proof systems. Theorem 3.2 (soundness) . If there exists a \mathsf{Q}\text{-}\mathsf{NS} - or \mathsf{Q}\text{-}\mathsf{SA} - or \mathsf{Q}\text{-}\mathsf{SOS} -refutation of \mathcal{Q}.\varphi , then \mathcal{Q}.\varphi is false. Proof. Suppose, for a contradiction, that \mathcal{Q}.\varphi is a true QBF, so the \exists -player has a winning strategy \sigma , but at the same time there is a refutation of \mathcal{Q}.\varphi of the form as in eq. ( 2 ) where all the variables in polynomials q_{u} are on the left of u and q is identically zero ( \mathsf{Q}\text{-}\mathsf{NS} ), or a polynomial with non-negative coefficients ( \mathsf{Q}\text{-}\mathsf{SA} ), or a sum of squares ( \mathsf{Q}\text{-}\mathsf{SOS} ). For every strategy \tau of the \forall -player, the game proceeds following the strategies \sigma and \tau and constructs a total Boolean assignment \alpha_{\sigma,\tau} satisfying the matrix \varphi . That is \sum_{p\in\enc(\varphi)}q_{p}p evaluates to 0 under every assignment \alpha_{\sigma,\tau} . For a universal variable u , we write \tau_{0 , and s_{u}<0 for u=1 ) and the absolute value encodes the magnitude of this preferred choice. If the existential player follows the choice, the universal player loses |s_{u}| points; otherwise he gains the same amount. Our interest in the score game is that the universal winning strategies can be transformed into \mathsf{Q}\text{-}\mathsf{NS} / \mathsf{Q}\text{-}\mathsf{SOS} refutations. Proposition 3.6 . A QBF \mathcal{Q}.\varphi is false if and only if the universal player has a winning strategy in the score game for \mathcal{Q}.\varphi (in either variant). Proof. Let the QBF \mathcal{Q}.\varphi be false. Then there exists a winning strategy \tau=(\tau_{u})_{u\in\vars_{\forall}(\mathcal{Q})} for the universal player in the evaluation game. In the score game, on the universal variable u the universal player plays depending on the total score S up to this point and \tau . The preferred choice of the universal player is \tau_{u} and he assigns to u score \displaystyle s_{u}=\begin{cases}0\quad&\text{if }S=1\ ,\\ (1-2\tau_{u})(1-S)\quad&\text{otherwise}\ .\end{cases} If in each step of the game the universal player gets always his preference \tau_{u} , then the matrix \varphi is falsified (since \tau is a winning strategy in the evaluation game). Otherwise, let u^{*} be the first variable where the universal player does not get his preference and S^{*} the total score before deciding the value for u . Since, by assumption the universal player does not get his preference but the value 1-\tau_{u^{*}} instead, then, after setting u^{*} , the total score is S^{*}+s_{u^{*}}(2(1-\tau_{u^{*}})-1)=1\ . (4) At this moment the universal player has essentially just won since he can set all following scores to 0 and the final total score of the game will be 1 . For the other direction, if the universal player has a winning strategy in the score game on \mathcal{Q}.\varphi then he wins also against the case when the existential player makes the scores negative in each moment of the game. In this case the resulting assignment must falsify the matrix \varphi since the universal player is using a winning strategy. As such, this strategy is also a winning strategy for the universal player in the usual evaluation game and the QBF \mathcal{Q}.\varphi is false. ∎ We require the universal strategy for each universal variable u to be expressed as a polynomial in all variables to the left of u in the quantifier prefix. The size of a universal strategy in the score game is then the sum of the number of monomials in all the s_{u} . Theorem 3.7 . Let \pi be a shortest \mathsf{Q}\text{-}\mathsf{SOS} (resp. \mathsf{Q}\text{-}\mathsf{NS} ) refutation of \mathcal{Q}.\varphi with respect to its Q-size. Then \qsize(\pi) equals the size of the shortest universal winning strategy in the score game in variant 1 (resp. variant 2 ) on \mathcal{Q}.\varphi . Proof. Let U=\vars_{\forall}(\mathcal{Q}) , let S be the size of the shortest universal winning strategy in the score game on \mathcal{Q}.\varphi , and let \pi be the LHS of a shortest \mathsf{Q}\text{-}\mathsf{SOS} (resp. \mathsf{Q}\text{-}\mathsf{NS} ) refutation written as \sum_{p\in\enc(\varphi)}q_{p}p+\sum_{u\in\mathrm{vars}_{\forall}(\mathcal{Q})}q_{u}(1-2u)+q=-1\ . (5) To show that \qsize(\pi)\geqslant S consider the universal strategy setting s_{u}=q_{u} . This is a winning strategy in the score game, i.e. for every total assignment \alpha the universal player wins the score game. Indeed, if \alpha falsifies \varphi then the universal player wins automatically (in both versions of the game). Assume then that \alpha satisfies \varphi , that is for every p\in\enc(\varphi) , \left.{p}\right|_{\alpha}=0 . Therefore, \pi evaluated at \alpha is the same as \sum_{u\in U}q_{u}(1-2u)+q evaluated at \alpha . The expression \sum_{u\in U}q_{u}(1-2u) evaluates under \alpha to -1 if \pi is a \mathsf{Q}\text{-}\mathsf{NS} refutation or to \leqslant-1<0 if \pi is a \mathsf{Q}\text{-}\mathsf{SOS} refutation. Therefore the total score when playing the game given the total assignment \alpha is \sum_{u\in U}s_{u}(2u-1)=\left.{\left(\sum_{u\in U}q_{u}(2u-1)\right)}\right|_{\alpha}=-\left.{\left(\sum_{u\in U}q_{u}(1-2u)\right)}\right|_{\alpha} and this latter sum equals 1 if \pi is a \mathsf{Q}\text{-}\mathsf{NS} refutation or it is >0 if \pi is a \mathsf{Q}\text{-}\mathsf{SOS} refutation. In other words the universal player in such cases wins using the scores. To prove \qsize(\pi)\leqslant S , we consider the cases where \pi is a \mathsf{Q}\text{-}\mathsf{NS} or \mathsf{Q}\text{-}\mathsf{SOS} refutation. Case 1: \pi is a \mathsf{Q}\text{-}\mathsf{NS} refutation. Let (s_{u})_{u\in U} be a shortest universal winning strategy for the score game in variant 2 on \mathcal{Q}.\varphi and let q_{u} be the polynomial computing s_{u} as a function of the variables left of u in \mathcal{Q} . In particular, on all Boolean assignments \alpha satisfying the matrix \varphi , the universal player wins because the total score is 1 , i.e. \left.{\left(\sum_{u\in U}q_{u}(1-2u)\right)}\right|_{\alpha}=-1 and therefore \sum_{u\in U}q_{u}(1-2u)+1 is in the ideal generated by the polynomials in \enc(\varphi) (this follows from 2.1 ). This gives a \mathsf{Q}\text{-}\mathsf{NS} refutation of \mathcal{Q}.\varphi with a Q-size of at most S . Case 2: \pi is a \mathsf{Q}\text{-}\mathsf{SOS} refutation. Let (s_{u})_{u\in U} be a shortest universal winning strategy for the score game in variant 2 on \mathcal{Q}.\varphi and let q_{u} be the polynomial computing s_{u} as a function of the variables left of u in \mathcal{Q} . For an assignment \alpha , let \score(\alpha)=\sum_{u\in U}s_{u}\left.{(2u-1)}\right|_{\alpha} . For every Boolean assignment \alpha satisfying the matrix \varphi , since (s_{u})_{u} is a winning strategy, we have \score(\alpha)>0 . That is for c=\frac{1}{2}\min_{\alpha\models\varphi}\score(\alpha) we have \sum_{u\in U}\frac{s_{u}}{c}(1-2u)=-\frac{\score(\alpha)}{c}<-1\ . (6) In this way, for every \alpha satisfying \varphi , 1-\frac{\score(\alpha)}{c}<0 . Let q=-\sum_{\alpha\models\varphi}\left(1-\frac{\score(\alpha)}{c}\right)\chi_{\alpha}(\boldsymbol{v})\ , where \chi_{\alpha}(\boldsymbol{v}) is the monomial which evaluates to 1 if the variables \boldsymbol{v} are set according to \alpha , and 0 on any other Boolean assignment. Modulo the polynomials v^{2}-v , q is a sum of squares, hence to conclude it is enough to notice that the polynomial \sum_{u\in U}\frac{1}{c}q_{u}(1-2u)+q+1 evaluates to 0 on every assignment satisfying \enc(\varphi) , hence it belongs to the ideal generated by the polynomials in \enc(\varphi) (this follows from 2.1 ). This gives a \mathsf{Q}\text{-}\mathsf{SOS} refutation of \mathcal{Q}.\varphi having the same \qsize as the strategy (s_{u})_{u} . ∎ Corollary 3.8 (completeness) . \mathsf{Q}\text{-}\mathsf{NS} / \mathsf{Q}\text{-}\mathsf{SA} / \mathsf{Q}\text{-}\mathsf{SOS} are complete. Proof. Proposition 3.6 and Theorem 3.7 immediately imply the completeness of \mathsf{Q}\text{-}\mathsf{NS} . As \mathsf{Q}\text{-}\mathsf{NS} refutations are special cases of \mathsf{Q}\text{-}\mathsf{SA} and \mathsf{Q}\text{-}\mathsf{SOS} refutations their completeness also follows. ∎ Alternatively, it is also possible to prove the completeness of \mathsf{Q}\text{-}\mathsf{NS} directly (without using the score game), as follows. Alternative proof of completeness of \mathsf{Q}\text{-}\mathsf{NS} . It is sufficient to show the completeness without twin variables. For this proof we use the encoding where \enc(x)=1-x , \enc(\neg x)=x , \enc(C)=\prod_{\ell\in C}\enc(\ell) . For a partial assignment \rho , let \textsf{Ind}(\rho) be the “indicator” polynomial that evaluates to 1 on all assignments extending \rho , and to 0 on all Boolean assignments that disagree with \rho . Formally, let \textsf{Ind}(\rho)=\prod_{x\in\rho^{-1}(1)}x\prod_{x\in\rho^{-1}(0)}(1-x)\ . Notice that if \rho falsifies C , then \enc(C) divides \textsf{Ind}(\rho) . Given a winning strategy S for the universal player in the evaluation game, we use it to prune the complete assignment tree, i.e. remove branches not consistent with S . Furthermore, we terminate a path as soon as a clause is falsified, and label the corresponding leaf with that falsified clause. (If there is more than one, pick any one arbitrarily.) This is a decision tree T which, given any assignment \alpha to the existential variables, finds a clause falsified by the assignment \alpha\cup S(\alpha) . The tree is unary-binary, since nodes labelled by universal variables have only one child. For a node v in the tree T , let \alpha_{v} denote the partial assignment leading to v . For the root node r , \alpha_{r}=\emptyset , and \textsf{Ind}(\alpha_{r})=1 . We show, by a bottom-up traversal, that for each node v , the polynomial \textsf{Ind}(\alpha_{v}) can be expressed as a polynomial combination of the initial clause encodings \{\enc(C)\mid C\in F\} and the universal polynomials (1-2u) , where the multipliers for 1-2u involve only variables quantified left of u . Case 1: v is a leaf, where clause C is falsified. In this case, \textsf{Ind}(\alpha_{v}) is a polynomial multiple of \enc(C) . Case 2: v is a node with two children, v_{0} and v_{1} . Then, for some existential variable x , \alpha_{v_{b}} extends \alpha_{v} by x=b . We have inductively expressed \textsf{Ind}(\alpha_{v_{b}}) for b=0,1 . Now \displaystyle\textsf{Ind}(\alpha_{v}) \displaystyle=\textsf{Ind}(\alpha_{v_{0}})+\textsf{Ind}(\alpha_{v_{1}})\ . \displaystyle\textsf{Ind}(\alpha_{v_{0}})+\textsf{Ind}(\alpha_{v_{1}}) \displaystyle=\textsf{Ind}(\alpha_{v})(1-x)+\textsf{Ind}(\alpha_{v})x \displaystyle=\textsf{Ind}(\alpha)v\ . Case 3: v is a node with one child w . Then for some universal variable u and some b , \alpha_{w} extends \alpha_{v} by u=b , and we have inductively expressed \textsf{Ind}(\alpha_{w}) . Consider b=0 , then \displaystyle 2\,\textsf{Ind}(\alpha_{w})-\textsf{Ind}(\alpha_{v})(1-2u) \displaystyle=2\,\textsf{Ind}(\alpha_{v})(1-u)-\textsf{Ind}(\alpha_{v})(1-2u) \displaystyle=\textsf{Ind}(\alpha_{v})\ . Since all variables in \alpha_{v} are quantified left of u , \textsf{Ind}(\alpha_{v}) is a valid multiplier for (1-2u) . Similarly if b=1 , then \displaystyle 2\,\textsf{Ind}(\alpha_{w})+\textsf{Ind}(\alpha_{v})(1-2u) \displaystyle=2\,\textsf{Ind}(\alpha_{v})u+\textsf{Ind}(\alpha_{v})(1-2u) \displaystyle=\textsf{Ind}(\alpha_{v})\ . Proceeding in this way all the way to the root, we get that \textsf{Ind}(\alpha_{r})=1 is expressible as a polynomial combination of the clause encodings and the universal polynomials with valid multipliers. ∎ 3.2 Upper bounds in \mathsf{Q}\text{-}\mathsf{SOS} via the score game Due to 3.7 , the score game can be used to obtain bounds on the Q-size of \mathsf{Q}\text{-}\mathsf{SOS} refutations. The advantage is being able to argue directly on countermodels (without reference to the syntactic representation of the matrix). To that end, we use QBFs Q\text{-}C_{n} from [ BBCP20 ] , which are defined via their countermodel computed by a family of circuits C_{n} . Definition 3.9 ( Q\text{-}C_{n} [ BBCP20 ] ) . Let n be an integer and C_{n} be a circuit with inputs x_{1},\dots,x_{n} and a single output. We define Q\text{-}C_{n}=\exists x_{1}\cdots\exists x_{n}\forall u\exists t_{1}\cdots\exists t_{m}.\big(u\nleftrightarrow C_{n}(x_{1},\dots,x_{n})\big)\ , where the additional variables t_{i} are used for a Tseitin-encoding of the circuit C_{n} into CNF (the i^{\text{th}} node in C_{n} is represented by variable t_{i} , and if, e.g., node i is an \land -gate between nodes j and k , then we have clauses encoding t_{i}\leftrightarrow(t_{j}\land t_{k}) , and similarly for \lor and \neg gates). For the Q\text{-}C_{n} formulas, the only countermodel sets u to C_{n}(x_{1},...,x_{n}) . Here, we are specifically interested in choosing circuits C_{n} that compute \textsf{Majority}_{n} . A circuit calculating \textsf{Majority}_{n} evaluates to true, if and only if at least half of the n input variables are set to true. We show that \textsf{Q-Majority}_{n} has short \mathsf{Q}\text{-}\mathsf{SOS} refutations in the \qsize measure. Proposition 3.10 . \textsf{Q-Majority}_{n} has \mathsf{Q}\text{-}\mathsf{SOS} refutations of linear \qsize . Proof. In the score game for \textsf{Q-Majority}_{n} , set s_{u}=-x_{1}-\cdots-x_{n}+\frac{n}{2}-\frac{1}{4} . The choice of the constant \frac{1}{4} is somewhat arbitrary, but should be between 0 and \frac{1}{2} . As there is only a single universal variable, this defines a complete strategy for the universal player. We show that s_{u} is a winning strategy. For an arbitrary assignment \alpha , \left.{s_{u}}\right|_{\alpha}<0 if and only if at least half of the existential x_{i} variables are set to 1, otherwise \left.{s_{u}}\right|_{\alpha}>0 . As such, the total score of the score game on \alpha is \left.{\big(-x_{1}-\cdots-x_{n}+\frac{n}{2}-\frac{1}{4}\big)(2u-1)}\right|_{\alpha} . This is negative only if either u=1 and at least half of the x_{i} equal 1 or u=0 and less then half of the x_{i} equal 1, i.e. if the matrix is satisfied, the score is positive. This strategy has size n+1 and degree 1 , hence, by 3.7 , there exists a \mathsf{Q}\text{-}\mathsf{SOS} refutation of \textsf{Q-Majority}_{n} with a \qsize linear in n . ∎ It is known that \textsf{Q-Majority}_{n} requires \mathsf{Q}\text{-}\mathsf{PC} refutations of exponential \qsize [ BHKS24 ] , therefore the previous result yields the exponential separation between \mathsf{Q}\text{-}\mathsf{PC} and \mathsf{Q}\text{-}\mathsf{SOS} in Figure 1 . 3.3 From existential Q-degree to Q-size In various proof systems, strong enough lower bounds on the degree/width of proofs immediately imply non-trivial lower bounds on proof size. This happens for instance in propositional proof systems such as Resolution [ BSW01 ] , Polynomial Calculus [ CEI96 ] , Sherali-Adams and Sum-of-Squares [ AH19 ] ; and in QBF proof systems as well, for instance in QU-Resolution [ BBMP23 ] , and Q-PC [ BHKS24 ] . It turns out that a very similar statement holds in \mathsf{Q}\text{-}\mathsf{SOS} between the existential Q-degree ( \qdeg(\cdot) , see 3.1 ) and Q-size ( \qsize(\cdot) , see 3.1 ). Theorem 3.11 . Let Q.\varphi be a false QBF with n variables that has a \mathsf{Q}\text{-}\mathsf{SOS} refutation of \qsize s . Then it has a \mathsf{Q}\text{-}\mathsf{SOS} refutation of \qdeg O(\sqrt{n\log s}) . The argument is similar to the proof of the analogous size-width inequality for Resolution from [ BSW01 ] . The main difference is the proof of the lemma below showing how to combine a proof of \qdeg k-1 of \mathcal{Q}.\varphi|_{x=1} and a proof of \qdeg k of \mathcal{Q}.\varphi|_{x=0} into a proof of \qdeg k of \mathcal{Q}.\varphi . This is done using the score game from the previous section. Lemma 3.12 . Let Q.\varphi be a false QBF and x\in\mathrm{vars}_{\exists}(\mathcal{Q}) . If there is a \mathsf{Q}\text{-}\mathsf{SOS} refutation \pi_{1} of Q.\varphi|_{x=1} with \qdeg(\pi_{1})\leqslant k-1 , and a \mathsf{Q}\text{-}\mathsf{SOS} refutation \pi_{0} of Q.\varphi|_{x=0} with \qdeg(\pi_{0})\leqslant k , then there is a \mathsf{Q}\text{-}\mathsf{SOS} refutation \pi of \mathcal{Q}.\varphi with \qdeg(\pi)\leqslant k . Proof. We consider the equivalent representation of the proofs as universal strategies in the score game. Let q_{1} be the final score in \pi_{1} and q_{0} be the final score in \pi_{0} . Let c be the maximum of \lvert q_{0}\rvert+1 over all assignments, and d be the smallest positive value that q_{1} can take (or 1 if q_{1} does not take positive values). For each u\in\mathrm{vars}_{\forall}(\mathcal{Q}) , let q_{u}=x\cdot q_{u}^{1}+\frac{d}{c}q_{u}^{0} , where q_{u}^{0} and q_{u}^{1} are the polynomials for u in \pi_{0} and \pi_{1} . Combining these q_{u} yields a strategy \pi with final score q=x\cdot q_{1}+\frac{d}{c}q_{0} and \qdeg(\pi)\leqslant k . We still need to argue that \pi is a universal winning strategy, i.e. that on every assignment \alpha satisfying \varphi we have q(\alpha)>0 . If \alpha sets x=0 , then it satisfies \varphi|_{x=0} , so q_{0}(\alpha)>0 due to the correctness of \pi_{0} . But if x=0 then q=0\cdot q_{1}+\frac{d}{c}q_{0}>0 . If \alpha sets x=1 , then it satisfies \varphi|_{x=1} , so q_{1}(\alpha)>0 due to the correctness of \pi_{1} . By the definitions of c and d , we have c>-q_{0}(\alpha) and d\leqslant q_{1}(\alpha) . This means that \frac{d}{c}q_{0}>-d\geqslant-q_{1}(\alpha) and q=1\cdot q_{1}+\frac{d}{c}q_{0}>0 . ∎ Lemma 3.13 . Let d,n,b\in\mathbb{N}^{\geqslant 0} and Q.\varphi be a false QBF. Let \pi be a \mathsf{Q}\text{-}\mathsf{SOS} refutation of Q.\varphi so that its q_{u} polynomials contain, in total, fewer than (1-\frac{d}{2n})^{-b} monomials of existential degree >d . Then there is a \mathsf{Q}\text{-}\mathsf{SOS} refutation \pi^{\prime} of Q.\varphi with \qdeg(\pi^{\prime})\leqslant d+b . Proof. The proof of this lemma is virtually identical to the proof of [ BSW01 , Theorem 3.5] . Informally, the proof is by an inductive argument on n and b , considering the high-degree monomials to be the ones with \qdeg at least d . By a counting argument there will be a literal x appearing in at least a \frac{d}{2n} fraction of them. Restricting by x=0 and x=1 , we have that the first restriction eliminates at least \frac{d}{2n} of the high-degree monomials, while the second eliminates one variable. Then using the inductive hypothesis and 3.12 concludes the argument. More formally, we fix d and prove the statement by induction over n and b . In the base cases where b=0 or n\leqslant d , \pi^{\prime}=\pi has the required \qdeg . Otherwise, we call those monomials high-degree which have existential degree >d . If \pi has k<(1-\frac{d}{2n})^{-b} high-degree monomials, they contain in total >kd existential literals. Because there are only 2n existential literals, one of these, say x , must occur in more than \frac{kd}{2n} high-degree monomials. When restricting \pi to x=0 , all these monomials vanish, leaving fewer than k-\frac{kd}{2n}=k(1-\frac{d}{2n})<(1-\frac{d}{2n})^{-(b-1)}<(1-\frac{d}{2(n-1)})^{-(b-1)} high-degree monomials. Applying the induction hypothesis yields a proof \pi_{0} of Q.\varphi|_{x=0} with \qdeg \leqslant d+b-1 . When restricting \pi to x=1 , the number of high-degree monomials certainly cannot increase, so it is at most k<(1-\frac{d}{2n})^{-b}<(1-\frac{d}{2(n-1)})^{-b} . Applying the induction hypothesis yields a proof \pi_{1} of Q.\varphi|_{x=1} with \qdeg \leqslant d+b . Finally, applying Lemma 3.12 to \pi_{0} and \pi_{1} yields a proof \pi^{\prime} of \qdeg \leqslant d+b . ∎ Given the two lemmas above it is immediate to prove 3.11 . Proof of 3.11 . Set b=d=\sqrt{2n\log s} and observe that s<(1-\frac{d}{2n})^{-b} . The number of high-degree monomials in the refutation is smaller than its total number of monomials s , so we can apply Lemma 3.13 and get a refutation of \qdeg(b+d)\in O(\sqrt{n\log s}) . ∎ 4 Lower bounds via strategy extraction in the evaluation game In QBF proof systems, strategy extraction is a welcome and ubiquitous feature. Informally, given a refutation of a false QBF, strategy extraction allows to represent in some computational model a winning strategy of the universal player in the evaluation game. Different QBF proof systems give rise to strategy extraction in different computational models. For example, from \mathsf{QU}\text{-}\textsf{Res} refutations we get unified decision lists [ BBMP23 ] and from Frege+ \forall -reduction refutations we get \mathsf{NC}_{1} circuits [ BBCP20 ] . In this section, we show that \mathsf{Q}\text{-}\mathsf{SOS} / \mathsf{Q}\text{-}\mathsf{SA} / \mathsf{Q}\text{-}\mathsf{NS} also admit strategy extraction, using polynomial threshold functions (PTF) as the computational model ( 4.3 ). We use this fact to prove a lower bound in \mathsf{Q}\text{-}\mathsf{SOS} ( 4.4 ) and a p-simulation of \mathsf{Q}\text{-}\mathsf{SOS} by Q-TC 0 -Frege ( 4.5 ). Definition 4.1 (polynomial threshold function) . A Boolean function f:\{0,1\}^{n}\to\{\pm 1\} is computed by a polynomial threshold function (PTF) , if there exists some n -variate polynomial p\in\mathbb{Q}[\boldsymbol{x}] such that f(\boldsymbol{x})=\sign(p(\boldsymbol{x})) . The size of the PTF is the number of monomials in p and the degree of the PTF is the degree of p . Remark 4.2 (On the PTF degree of parity) . It is well known that f(\boldsymbol{x})=x_{1}\oplus x_{2}\oplus\cdots\oplus x_{n} cannot be computed by PTFs of degree less than n . We recall briefly the argument (see also for instance [ MP87 ] ). Let f(\boldsymbol{x})=\sign(p(\boldsymbol{x})) with p a n -variate polynomial of degree d . Since f is symmetric, there exists a symmetric n variate polynomial p^{\prime} such that f(\boldsymbol{x})=\sign(p^{\prime}(\boldsymbol{x})) and \deg(p^{\prime})\leqslant\deg(p)=d . Since p^{\prime} is symmetric, there exists a univariate polynomial p^{\prime\prime} such that p^{\prime\prime}(x_{1}+\cdots+x_{n})=p^{\prime}(\boldsymbol{x}) and \deg(p^{\prime\prime})=\deg(p^{\prime}) . In other words, f(\boldsymbol{x})=\sign(p^{\prime\prime}(x_{1}+\dots+x_{n})) . To conclude it is enough to notice that on 0 , 1 , \dots , n the polynomial p^{\prime\prime} must be alternating signs and hence it must have at least n real roots; therefore d\geqslant\deg(p^{\prime\prime})\geqslant n . Given a \mathsf{Q}\text{-}\mathsf{SOS} / \mathsf{Q}\text{-}\mathsf{SA} / \mathsf{Q}\text{-}\mathsf{NS} refutation \sum_{p\in\enc(\varphi)}q_{p}p+\sum_{u\in\mathrm{vars}_{\forall}(\mathcal{Q})}q_{u}(1-2u)+q+1=0 of a false QBF \mathcal{Q}.\varphi , we claim that for every universal variable u , \sign(q_{u}) computes a strategy for 1-2u . 1 1 1 We use the convention that \sign(0)=+1 . This can then be easily transformed into a strategy for u through a linear output transformation mapping -1 to 1 and 1 to 0 . Per definition, for every universal variable u , \sign(q_{u}) is a PTF. The size of the extracted strategy is the sum of the sizes of the PTFs and, as such, the Q-size of the refutation. Analogously, the degree of the extracted strategy, i.e. the maximum degree of the PTFs, equals the total Q-degree of the refutation. Theorem 4.3 . Let \sum_{p\in\enc(\varphi)}q_{p}p+\sum_{u\in\mathrm{vars}_{\forall}(\mathcal{Q})}q_{u}(1-2u)+q+1=0 be a \mathsf{Q}\text{-}\mathsf{SOS} / \mathsf{Q}\text{-}\mathsf{SA} / \mathsf{Q}\text{-}\mathsf{NS} proof of a false QBF \mathcal{Q}.\varphi . Then the universal strategy that maps each universal variable u\in\vars_{\forall}(\mathcal{Q}) to \frac{1}{2}(1-\sign(q_{u})) is a countermodel (i.e. falsifies \varphi ). Proof. The syntactic restriction of countermodels, i.e. that each variable only depends on variables left of it in the quantifier prefix \mathcal{Q} , holds by definition of q_{u} . For every universal variable u played according to the strategy, we have q_{u}(1-2u)=q_{u}\sign(q_{u})\geqslant 0 . As such, \sum_{u\in\vars_{\forall}(\mathcal{Q})}q_{u}(1-2u)+q+1\geqslant 1 . Hence, \sum_{p\in\enc(\varphi)}q_{p}p\leqslant-1 , which is only possible if the matrix \varphi is not satisfied (otherwise q_{p}p=0 for all p\in\enc(\varphi) ). ∎ To exemplify the strategy extraction technique for \mathsf{Q}\text{-}\mathsf{SOS} , we use 4.2 and 4.3 to prove that the Parity formulas [ BCJ15 ] \textsf{Parity}_{n}=\exists x_{1}\cdots\exists x_{n}\forall u\exists t_{1}\cdots\exists t_{n}.\ (t_{1}\leftrightarrow x_{1})\land(u\nleftrightarrow t_{n})\land\bigwedge_{i=2}^{n}(t_{i}\leftrightarrow t_{i-1}\oplus x_{i}). are exponentially hard for \mathsf{Q}\text{-}\mathsf{SOS} . Notice that the only winning strategy for the universal player is to set u=x_{1}\oplus\dots\oplus x_{n} . Corollary 4.4 . Every \mathsf{Q}\text{-}\mathsf{SOS} refutation of \textsf{Parity}_{n} requires Q-size \exp(\Omega(n)) . Proof. Let d:=\qdeg(\pi) and apply strategy extraction ( 4.3 ) to get a PTF of degree d that computes u=\bigoplus_{i=1}^{n}x_{i} . By 4.2 , its degree is at least n , so d\geqslant n . Let s:=\qsize(\pi) and apply Theorem 3.11 to obtain n\leqslant d=O(\sqrt{n\log s}) and therefore s=\exp(\Omega(n)) . Theorem 3.11 can be applied here, because \textsf{Parity}_{n} only has a single universal variable and, as such, its existential Q-degree equals its total Q-degree. ∎ As a second consequence of 4.3 , strategy extraction can also be used to embed \mathsf{Q}\text{-}\mathsf{SOS} into more powerful systems, in this case Q-TC 0 -Frege . Q-TC 0 -Frege is the \mathsf{TC}_{0}\text{-}\mathsf{Frege} system with an added universal reduction rule. The Q-size of a Q-TC 0 -Frege refutation is the sum of the number of symbols of all lines involved in a \forall -reduction step. Corollary 4.5 . Q-TC 0 -Frege p-simulates \mathsf{Q}\text{-}\mathsf{SOS} in the \qsize measure. Proof. We extract PTFs calculating a countermodel for the QBF from \mathsf{Q}\text{-}\mathsf{SOS} refutations. A PTF can be transformed into a depth-2 threshold circuit as follows. Every monomial can be seen as an AND Gate, since we are only interested in Boolean assignments. In the second layer, we can use a single weighted linear threshold function using the AND gates as inputs. It is known that the \qsize of Q-TC 0 -Frege refutations is characterized by the size of expressing the strategy in \mathsf{TC}_{0} circuits [ BBCP20 ] . As such, there exists a Q-TC 0 -Frege proof of \qsize bounded by the size of the \mathsf{TC}_{0} circuit computing the countermodel, which itself is bounded by the \qsize of the \mathsf{Q}\text{-}\mathsf{SOS} refutation. ∎ 5 Lower bounds via Q-pseudo-expectation In the propositional setting, the notion of pseudo-expectation is the standard tool to obtain degree lower bounds for \mathsf{SOS} , see for instance [ FKP19 ] . Thanks to the size-degree relation for \mathsf{SOS} [ AH19 ] , degree lower bounds also give size lower bounds. Inspired by the propositional notion of pseudo-expectation, we give a notion of pseudo-expectation for \mathsf{Q}\text{-}\mathsf{SOS} and use it to prove lower bounds on the \qdeg of \mathsf{Q}\text{-}\mathsf{SOS} refutations. In particular, for a false QBF \mathcal{Q}.\varphi and a \mathsf{Q}\text{-}\mathsf{SOS} expression \pi of the form \sum_{p\in\enc(\varphi)}q_{p}p+\sum_{u\in\mathrm{vars}_{\forall}(\mathcal{Q})}q_{u}(1-2u)+q+1\ , (7) where all the variables in q_{u} are on the left of u in \mathcal{Q} and q is a sum of squares, we consider witnesses that \pi\neq 0 , i.e. that \pi is not a \mathsf{Q}\text{-}\mathsf{SOS} refutation of \mathcal{Q}.\varphi . In analogy to the propositional case, we call the witnesses we construct Q-pseudo-expectations . Definition 5.1 (Q-pseudo-expectation in \mathsf{Q}\text{-}\mathsf{SOS} ) . Given \mathcal{Q}.\varphi and a \mathsf{Q}\text{-}\mathsf{SOS} expression \pi as in eq. ( 7 ), a Q-pseudo-expectation for \mathcal{Q}.\varphi and \pi is a linear function \tilde{\mathbb{E}}\colon\mathbb{Q}[V\cup\overline{V}]\to\mathbb{R} such that: 1. \tilde{\mathbb{E}}[1]=1 ; 2. \tilde{\mathbb{E}}[q+\sum_{p\in\enc(\varphi)}q_{p}p]\geqslant 0 ; 3. \tilde{\mathbb{E}}[\sum_{u\in\vars_{\forall}(\mathcal{Q})}q_{u}(1-2u)]\geqslant 0 . In the propositional context, a single pseudo-expectation for \mathsf{SOS} typically targets a fixed degree d and has properties similar to 1.–3. above but for arbitrary q_{p} and sum-of-squares q such that the degree of q_{p}p and q are at most d . In this way, a single pseudo-expectation rules out the possibility of any small-degree \mathsf{SOS} refutation. There are exceptions to this general approach, for instance the pseudo-expectations used in [ Hak20 ] that are targeting all \mathsf{SOS} proofs over a certain set of monomials, but we are not aware of degree lower bounds in \mathsf{SOS} proved by constructing a family of pseudo-expectations each tailored to a specific set of polynomials (i.e. as in 5.1 but without the condition in item 3.). In the QBF context, this is what we do. To rule out small \qdeg \mathsf{Q}\text{-}\mathsf{SOS} refutations we use a family of pseudo-expectations, each targeting one possible candidate \mathsf{Q}\text{-}\mathsf{SOS} proof, i.e. an expression as in eq. ( 7 ). We formalise this approach in 5.2 and exemplify it in 5.3 . Theorem 5.2 . Given a QBF \mathcal{Q}.\varphi , if for every \mathsf{Q}\text{-}\mathsf{SOS} expression \pi as in eq. ( 7 ) with \qdeg(\pi)0, • for each (C,w)\in\mathcal{L}_{k},w\geqslant 0, • \mathcal{L}_{i+1} is obtained from \mathcal{L}_{i} by the use of one of the following substitution rules: Universal Reduction \dfrac{(C\lor u,2w)}{(C,w)} , where all the variables in C are on the left of u in the quantifier prefix \mathcal{Q} and u is a universal variable, Axiom \dfrac{\phantom{(C,w)}}{(C,w)} , where C is a clause in \varphi , w\in\mathbb{Z} , Symmetric Cut \dfrac{(C\lor x,w)\quad(C\lor\neg x,w)}{(C,w)} with w\in\mathbb{Z} , Idempotency \dfrac{(C\lor x\lor x,w)}{(C\lor x,w)} with w\in\mathbb{Z} . The \size of a Q-w-Res refutation is the number of lines in the proof, and the Q-size is the number of universal reduction steps. We say that two configurations are equivalent, if the total weight of each clause is the same in both. For example, \{(C,w),(C,v)\} is equivalent to \{(C,w+v)\} . Additionally, every configuration is implicitly assumed to contain every clause with weight 0. These two properties combined allows one to use every clause (C,w) for some rule, as long as (C,-w) is also added to the next configuration. (In 6.1 , we implicitly allow that \mathcal{L}_{i+1} is equivalent to some configuration obtained from another configuration equivalent to \mathcal{L}_{i} by the use of one of the substitution rules.) Note that every rule of Q-w-Res can also be used in the reverse direction. The “reverse” rules are not required to be defined as such, because this is equivalent to using the “forward” rules with negative weights. For example, the reverse of the symmetric cut rule is removing (C,w) from the configuration and adding (C\lor x,w) and (C\lor\neg x,w) . This is the same as adding (C,-w) and removing (C\lor x,-w) and (C\lor\neg x,-w) due to the equivalence definition. Recall that clause C=\bigvee_{v\in P}v\lor\bigvee_{v\in N}\lnot v is encoded as the set of polynomials \enc(C)=\left\{\prod_{v\in P}\overline{v}\prod_{v\in N}v\right\}\cup\{v^{2}-v,\ v+\overline{v}-1:v\in P\cup N\}\ . Let M(C)=\prod_{v\in P}\overline{v}\prod_{v\in N}v be the monomial associated to C in \enc(C) . It is easy to see that multi-sets of weighted clauses and polynomials are just two ways of describing the same objects. The configuration \{(C_{1},a_{1}),...,(C_{n},a_{n})\} corresponds to the polynomial \sum_{i=1}^{n}-a_{i}\mathsf{M}(C_{i}) and the polynomial \sum_{i=1}^{n}a_{i}\prod_{j\in N_{i}}\overline{x_{j}}\prod_{j\in P_{i}}x_{j} corresponds to the configuration \{(\bigvee_{j\in N_{i}}x_{j}\lor\bigvee_{j\in P_{i}}\neg x_{j},-a_{i}):i\in\{1,...,n\}\} . This isomorphism preserves equivalence [ BBL24 ] . Lemma 6.2 ( [ BBL24 ] ) . Let configurations of weighted clauses \mathcal{L}_{1} and \mathcal{L}_{2} be given. \mathcal{L}_{1} and \mathcal{L}_{2} are equivalent if and only if \sum_{(C,w)\in\mathcal{L}_{1}}w\mathsf{M}(C)=\sum_{(C,w)\in\mathcal{L}_{2}}w\mathsf{M}(C). Proposition 6.3 . Q-w-Res is polynomially equivalent to \mathsf{Q}\text{-}\mathsf{SA} in both the \size and \qsize measure. Proof. This proof is completely analogous to the equivalence in the propositional case between \mathsf{SA} and \mathsf{w} - Res [ BBL24 ] . It suffices to show that the method can be extended for the respective reduction rules. \mathsf{Q}\text{-}\mathsf{SA} p-simulates Q-w-Res Let \mathcal{L}_{1},...,\mathcal{L}_{t} be a Q-w-Res refutation of some false QBF \mathcal{Q}.\bigwedge_{j=1}^{m}C_{j} . We construct algebraic expressions S_{1},...,S_{t} having the form of a \mathsf{Q}\text{-}\mathsf{SA} derivation, with the property that S_{i}=-\sum_{(C,w)\in\mathcal{L}_{i}}w\cdot\mathsf{M}(C) . That is, each S_{i} is constructed as a sum of (i) multiples of the polynomials in \enc(C_{j}) for some j (recall, this encoding includes the Boolean and the twin variable axioms), and (ii) multiples of (1-2u) for some universal variable u , where the multiplier polynomials depend only on variables quantified left of u . Let S_{1}=0 . Since \mathcal{L}_{1}=\emptyset this fulfils our requirement. Now suppose we have constructed an algebraic expression S_{i} that equals -\sum_{(C,w)\in\mathcal{L}_{i}}w\cdot\mathsf{M}(C) . We want to construct S_{i+1} . We differentiate between the rules used to obtain \mathcal{L}_{i+1} . Note that only the first case is new to the QBF variant, all the other cases are completely analogous to the propositional case. We write them anyway for completeness. • If \mathcal{L}_{i+1} is obtained from \mathcal{L}_{i} by a universal reduction rule \frac{(C\lor u,2w)}{(C,w)} , then add to S_{i} the terms 2w\mathsf{M}(C\lor u)-w\mathsf{M}(C)=-w\mathsf{M}(C)(1-2u). That is S_{i+1}=S_{i}-w\mathsf{M}(C)(1-2u) . • If \mathcal{L}_{i+1} is obtained from \mathcal{L}_{i} by an axiom rule \frac{}{(C,w)} , then add to S_{i} the term -w\mathsf{M}(C) . That is S_{i+1}=S_{i}-w\mathsf{M}(C) . • If \mathcal{L}_{i+1} is obtained from \mathcal{L}_{i} by an idempotency rule \frac{(C\lor x\lor x)}{(C\lor x,w)} , then add to S_{i} the terms w\mathsf{M}(C\lor x\lor x)-w\mathsf{M}(C\lor x)=w\mathsf{M}(C)(x^{2}-x). That is S_{i+1}=S_{i}+w\mathsf{M}(C)(x^{2}-x) . • If \mathcal{L}_{i+1} is obtained from \mathcal{L}_{i} by a symmetric cut rule \frac{(C\lor x,w)\hskip 8.19447pt(C\lor\neg x,w)}{(C,w)} , then add to S_{i} the terms -w\mathsf{M}(C)+w\mathsf{M}(C\lor x)+w\mathsf{M}(C\lor\neg x)=w\mathsf{M}(C)(x+\overline{x}-1). That is S_{i+1}=S_{i}+w\mathsf{M}(C)(x+\overline{x}-1) . One can easily verify, that S_{i+1} constructed as above, fulfils S_{i+1}=-\sum_{(C,w)\in\mathcal{L}_{i}}w\mathsf{M}(C) and in particular S_{t}=-\sum_{(C,w)\in\mathcal{L}_{t}}w\mathsf{M}(C) . Since \mathcal{L}_{t} contains only an empty clause (\bot,c) for some c>0 and clauses with positive weights, S_{t}=-c-q for some polynomial q having only positive coefficients. Therefore \frac{S_{t}}{c}+\frac{q}{c}+1=0 is a \mathsf{Q}\text{-}\mathsf{SA} refutation, and its size is no more than the size of the Q-w-Res refutation. The only times a monomial added to S_{i} contributes to \qsize is in the first case, if \mathcal{L}_{i+1} is obtained by the universal reduction rule. As a result, the \qsize of the resulting \mathsf{Q}\text{-}\mathsf{SA} proof is exactly the number of reduction steps, i.e. the \qsize of the Q-w-Res proof. Q-w-Res p-simulates \mathsf{Q}\text{-}\mathsf{SA} Let \sum_{p\in\enc(\varphi)}q_{p}p+\sum_{u\in\mathrm{vars}_{\forall}(\mathcal{Q})}q_{u}(1-2u)+q+1=0 (12) be a \mathsf{Q}\text{-}\mathsf{SA} refutation of a false QBF \mathcal{Q}.\varphi . We split \enc(\varphi) into the encoding of the clauses of \varphi P, the Boolean axioms B and the twin variable axioms T , such that ( 12 ) is equivalent to \sum_{p\in P}q_{p}p+\sum_{b\in B}q_{b}b+\sum_{t\in T}q_{t}t+\sum_{u\in\mathrm{vars}_{\forall}(\mathcal{Q})}q_{u}(1-2u)+q+1=0. (13) Without loss of generality, q_{p} can be non-positive scalars for all p\in P (cf. Lemma 5.4 in [ BBL24 ] ; the universal terms are untouched). Therefore, we can rewrite ( 13 ) as -1-q=\sum_{p\in P}-a_{p}p+\sum_{b\in B}q_{b}b+\sum_{t\in T}q_{t}t+\sum_{u\in\mathrm{vars}_{\forall}(\mathcal{Q})}q_{u}(1-2u) (14) for scalars a_{p}\geqslant 0 . We construct a Q-w-Res proof (\mathcal{L}_{1},...,\mathcal{L}_{t}) of \mathcal{Q}.\varphi . This is achieved by going through the right-hand side of ( 14 ) term by term and constructing sets of weighted clauses corresponding to these partial sums. Additionally, each set of weighted clauses can be constructed by the previous set and a Q-w-Res rule. We start with the empty sum and set \mathcal{L}_{1}=\emptyset . There is nothing to show. Every clause (C_{i},a_{i}) corresponds to the term -a_{i}\mathsf{M}(C_{i}) . Therefore, we can construct a sequence of configurations \mathcal{L}_{2},...,\mathcal{L}_{k_{1}} , with each \mathcal{L}_{i}=\{(C_{1},a_{1}),...,(C_{i-1},a_{i-1})\} corresponding to the i-1 -th partial sum of \sum_{p\in P}-a_{p}p . In this sequence, each configuration is obtained with the previous one and the axiom rule. Continuing, for every binomial am(x^{2}-x) from the sum \sum_{b\in B}q_{b}b construct \mathcal{L}_{k_{2}}=\mathcal{L}_{k_{2}-1}\cup\{(C\lor\neg x\lor\neg x,-a),(C\lor\neg x,a)\} where C is the unique clause such that \mathsf{M}(C)=m . This is an application of the idempotency rule. Analogously, every term am(x_{i}+\overline{x}_{i}-1) from the sum \sum_{t\in T}q_{t}t constructs \mathcal{L}_{k_{3}}=\mathcal{L}_{k_{3}-1}\cup\{(C\lor\neg x,-a),(C\lor x,-a),(C,a)\}, with C again being the unique clause such that \mathsf{M}(C)=m . This is an application of the symmetric cut rule. This construction is extended to the terms am(1-2u) from \sum_{u\in\vars_{\forall}(\mathcal{Q})}q_{u}(1-2u) . Here \mathcal{L}_{k_{4}}=\mathcal{L}_{k_{4}-1}\cup\{(C\lor\neg u,2a),(C,-a)\}. This corresponds to the universal reduction rule. Due to these terms being obtained from a \mathsf{Q}\text{-}\mathsf{SA} refutation, the syntactic restrictions for the reduction rule, i.e. C only containing variables left of u and u being universal, are met. Equation ( 14 ) shows that this resulting configuration is equivalent to \mathcal{L}_{t}=\{(\bot,1)\}\cup\{(C_{i},a_{i}):-q=\sum_{i}-a_{i}\mathsf{M}(C_{i})\} for clauses C_{i} and non-negative scalars a_{i} . This representation of q is possible due to the definition of \mathsf{Q}\text{-}\mathsf{SA} . As such, (\mathcal{L}_{1},...,\mathcal{L}_{t}) is a Q-w-Res refutation of \mathcal{Q}.\varphi with rational weights, and a suitable multiple gives an integral version matching 6.1 . For every monomial in q_{u} , exactly one universal reduction is added. As such, the Q-sizes match. ∎ 7 Simulations We now investigate how the algebraic QBF systems relate to each other and to other known QBF proof systems such as QU-Resolution and Q-PC and show the p-simulations of Figure 1 . Theorem 7.1 . \mathsf{Q}\text{-}\mathsf{SOS} p-simulates \mathsf{Q}\text{-}\mathsf{SA} w.r.t. the \size and \qsize measures. Proof. It is well known that (degree 2d ) \mathsf{SOS} p-simulates (degree d ) \mathsf{SA} (see for instance [ FKP19 , Lemma 3.63] ). The same argument works without change in the QBF setting: every variable v in a positive monomial can be substituted by v^{2} summing a suitable multiple of v^{2}-v . In this way, every positive monomial \frac{a}{b}m with a,b\in\mathbb{N} can be converted into \frac{s_{1}^{2}+s_{2}^{2}+s_{3}^{2}+s_{4}^{2}}{b^{2}}m^{2} where s_{1},s_{2},s_{3},s_{4} are four integers that sum up to ab (they exists by Lagrange’s Four Squares Theorem). This converts \frac{a}{b}m into a sum of at most four squares with rational coefficients. ∎ In the argument above, notice that the only increment in degree is in the propositional part, hence, different from the propositional case, \mathsf{Q}\text{-}\mathsf{SOS} with \qdeg d p-simulates \mathsf{Q}\text{-}\mathsf{SA} with \qdeg d . In the \qsize measure, the converse also holds. Theorem 7.2 . \mathsf{Q}\text{-}\mathsf{SA} p-simulates \mathsf{Q}\text{-}\mathsf{SOS} w.r.t. the \qsize measure. Proof. Every polynomial q that is non-negative on the Boolean assignments can be written as a (possibly exponentially large) sum of the form \sum_{\alpha}\left.{q}\right|_{\alpha}\chi_{\alpha}(\boldsymbol{v}) , where \chi_{\alpha}(\boldsymbol{v}) is a monomial that evaluates to 1 when the variables are set according to the Boolean assignment \alpha and on any other Boolean assignment it is 0 . In other words, every \mathsf{Q}\text{-}\mathsf{SOS} refutation can be written as a possibly exponentially larger \mathsf{Q}\text{-}\mathsf{SA} refutation. The exponential blow-up appears in the propositional part which is not accounted for in \qsize . ∎ Theorem 7.3 . \mathsf{Q}\text{-}\mathsf{SA} p-simulates \mathsf{QU}\text{-}\textsf{Res} w.r.t. both \size and \qsize . Proof. Due to 6.3 , to show that \mathsf{Q}\text{-}\mathsf{SA} p-simulates \mathsf{QU}\text{-}\textsf{Res} it is enough to show that Q-w-Res p-simulates \mathsf{QU}\text{-}\textsf{Res} . This p-simulation is an adaptation of the proof that \mathsf{w} - Res p-simulates Res [ BBL24 ] . This proof is done in two steps. First, we show that every resolution step in a \mathsf{QU}\text{-}\textsf{Res} refutation can be transformed into a sequence of weakening and symmetric cut rules. Second, we then add appropriate weights to the clauses to transform it into a Q-w-Res refutation. Let \frac{(C\lor D\lor x)\quad(C\lor E\lor\neg x)}{(C\lor D\lor E)} be an arbitrary application of the resolution rule in a \mathsf{QU}\text{-}\textsf{Res} refutation, where C,D,E are clauses with pairwise disjoint variables and none containing x or \neg x . Let D consist of literals d_{1},d_{2},...,d_{k} and E of literals e_{1},e_{2},...,e_{\ell} . Using \ell consecutive weakening rules, we expand (C\lor D\lor x) to (C\lor D\lor E\lor x) and (C\lor E\lor\neg x) to (C\lor D\lor E\lor\neg x) . These two clauses can then be used in a single symmetric cut to gain (C\lor D\lor E) . For the second step, we need to add weights to the clauses. Since \mathsf{QU}\text{-}\textsf{Res} proofs in general are not treelike, we need to chose the weights in a way that keeps all previous clauses in the configuration. Let \pi=C_{1},...,C_{t} be an arbitrary \mathsf{QU}\text{-}\textsf{Res} refutation of a false QBF, using symmetric cut instead of resolution. We inductively construct a sequence of configurations \mathcal{L}_{1},...,\mathcal{L}_{t} , such that these are a valid Q-w-Res proof and for every i\leqslant t there exist strictly positive weights w_{1}^{i},...,w_{i}^{i} with \{(C_{j},w_{j}^{i}),j\in\{1,...,i\}\}\subseteq\mathcal{L}_{i} . Additionally, all the weights in every \mathcal{L}_{i} are non-negative. We differentiate between the rules used to obtain C_{i} . • C_{i} is an axiom. Then \mathcal{L}_{i}=\mathcal{L}_{i-1}\cup\{(C_{i},1)\} and \mathcal{L}_{i} is obtained from \mathcal{L}_{i-1} using the axiom rule. • C_{i} is obtained from C_{j} using the universal reduction rule, i.e. C_{j}=C_{i}\lor u for some universal literal u . Let w_{j} be the weight such that (C_{j},w_{j})\in\mathcal{L}_{i-1} . Then \mathcal{L}_{i}=\mathcal{L}_{i-1}\cup\{(C_{j},-\frac{w_{j}}{2})\}\cup\{(C_{i},\frac{w_{j}}{4})\} and \mathcal{L}_{i} is obtained from \mathcal{L}_{i-1} using the universal reduction rule. • C_{i} is obtained from C_{j} using the weakening rule, i.e. C_{i}=C_{j}\lor v for some literal v . Let w_{j} be the weight such that (C_{j},w_{j})\in\mathcal{L}_{i-1} . Then \mathcal{L}_{i}=\mathcal{L}_{i-1}\cup\{(C_{j},-\frac{w_{j}}{2})\}\cup\{(C_{i},\frac{w_{j}}{2}),(C_{j}\lor\neg v,\frac{w_{j}}{2})\} and \mathcal{L}_{i} is obtained from \mathcal{L}_{i-1} using the symmetric rule. • C_{i} is obtained from C_{j} and C_{k} using the symmetric cut rule, i.e. C_{j}=C_{i}\lor v and C_{k}=C_{i}\lor\neg v for some variable v . Let w_{j} and w_{k} be the weights such that (C_{j},w_{j}),(C_{k},w_{k})\in\mathcal{L}_{i-1} and define w=\min\{w_{j},w_{k}\} . Then \mathcal{L}_{i}=\mathcal{L}_{i-1}\cup\{(C_{j},-\frac{w}{2}),(C_{k},-\frac{w}{2})\}\cup\{(C_{i},\frac{w}{2})\} and \mathcal{L}_{i} is obtained from \mathcal{L}_{i-1} using the symmetric cut rule. The non-negativity of all weights follow directly. Since \pi is a \mathsf{QU}\text{-}\textsf{Res} proof, C_{t}=\bot . As such, there exists some weight w_{t}>0 with (\bot,w_{t})\in\mathcal{L}_{t} . Thus \mathcal{L}_{1},...,\mathcal{L}_{t} is a valid Q-w-Res refutation with rational weights, and a suitable multiple gives an integral version matching 6.1 . In total, for every resolution rule of \pi we add at most n lines to the Q-w-Res proof and for every reduction rule we add exactly one line (where n is the number of variables). The resulting proof has size at most n|\pi| , and its Q-size is \qsize(\pi) . ∎ Theorem 7.4 . \mathsf{Q}\text{-}\mathsf{PC} p-simulates \mathsf{Q}\text{-}\mathsf{NS} w.r.t. the \size and \qsize measures. Proof. Let \mathcal{Q}.\varphi be a false QBF with n variables and m clauses and \pi be a \mathsf{Q}\text{-}\mathsf{NS} refutation of \mathcal{Q}.\varphi of the form \sum_{p\in\enc(\varphi)}q_{p}p+\sum_{u\in\mathrm{vars}_{\forall}(\mathcal{Q})}q_{u}(1-2u)+1=0\ , (15) Lines in a \mathsf{Q}\text{-}\mathsf{PC} proof can be multiplied by arbitrary polynomials. Hence, we can obtain in \mathsf{Q}\text{-}\mathsf{PC} the sum \sum_{p\in\enc(\varphi)}q_{p}p from the polynomials in \enc(\varphi) in a polynomial number of steps. Let \vars_{\forall}(\mathcal{Q}) be u_{1},u_{2},\dots,u_{n} . Due to the symbolic equality in eq. ( 15 ), this sum equals -1-\sum_{i=1}^{n}q_{u_{i}}(1-2u_{i}) . We then use the \forall -reduction on u_{n} , then u_{n-1} etc. In the first step, restricting by u_{n}=1 and u_{n}=0 , we get respectively -1-\sum_{i=1}^{n-1}q_{u_{i}}(1-2u_{i})-q_{u_{n}}\text{\ and\ }-1-\sum_{i=1}^{n-1}q_{u_{i}}(1-2u_{i})+q_{u_{n}}\ . Adding them, we get -1-\sum_{i=1}^{n-1}q_{u_{i}}(1-2u_{i}) . We repeat this process until we get rid of all universal variables and only the -1 remains. It is clear from the argument that this simulation only increases the \size and \qsize linearly. ∎ Theorem 7.5 . \mathsf{Q}\text{-}\mathsf{SOS} p-simulates \mathsf{Q}\text{-}\mathsf{PC} w.r.t. the \size and \qsize measures. Proof. (sketch) The argument in [ Ber18 , Lemma 3.1] showing that degree 2d \mathsf{SOS} p-simulates degree d \mathsf{PC} adapts easily to the QBF setting. The idea is that given a \mathsf{Q}\text{-}\mathsf{PC} derivation p_{1},\dots,p_{s} we derive an algebraic expression for -p_{i}^{2} which eventually for i=s will give a \mathsf{Q}\text{-}\mathsf{SOS} refutation of \mathcal{Q}.\varphi . This is done inductively on i and is based on the following algebraic identities: • sum rule (from p and q deduce ap+bq with a,b\in\mathbb{Q} ): -(ap+bq)^{2}=-2a^{2}p^{2}-2b^{2}q^{2}+(ap-bq)^{2}\ ; • product rule (from p deduce xp ): -(xp)^{2}=-p^{2}+(p-xp)^{2}+2p^{2}(x-x^{2})\ ; • \forall -reduction (from p+qu deduce p ): -p^{2}=-2(p+qu)^{2}+(p+q)^{2}-(q^{2}+2pq)(1-2u)+2q^{2}(u^{2}-u)\ ; • \forall -reduction (from p+qu deduce p+q ): -(p+q)^{2}=-2(p+qu)^{2}+p^{2}-(q^{2}+2pq)(1-2u)+2q^{2}(u^{2}-u)\ . ∎ Corollary 7.6 . \mathsf{Q}\text{-}\mathsf{SOS} p-simulates \mathsf{Q}\text{-}\mathsf{NS} and is exponentially stronger, w.r.t. the \size and \qsize measures. Proof. The simulation follows from 7.5 and 7.4 . The separation follows from 3.10 and 7.4 for the \qsize measure, and from propositional separations [ ALN16 , DGGM24 ] for the \size measure. ∎ 8 Conclusion In this work we defined semi-algebraic proof systems for QBF and initiated their proof complexity investigation. While our results already reveal an interesting picture in terms of simulations and lower and upper bounds, a number of questions remain that appear to be of interest for further research. In the propositional setting Res and \mathsf{NS} are incomparable proof systems. Are also \mathsf{Q}\text{-}\mathsf{NS} and \mathsf{QU}\text{-}\textsf{Res} incomparable w.r.t. the \qsize measure? In section 4 we showed how to express strategy extraction for \mathsf{Q}\text{-}\mathsf{SOS} using polynomial threshold functions. Although this suffices for lower bounds, it appears interesting to determine the correct computational model characterizing strategy extraction for \mathsf{Q}\text{-}\mathsf{SOS} and \mathsf{Q}\text{-}\mathsf{NS} in the same sense as the tight characterisations for \mathsf{QU}\text{-}\textsf{Res} [ BBMP23 ] , \mathsf{Q}\text{-}\mathsf{PC} [ BHKS24 ] , and QBF Frege systems [ BBCP20 ] . Finally, it would be interesting to determine the relationship of our new semi-algebraic QBF systems to the static expansion-based algebraic systems suggested in [ CCKS23 ] , which might turn out to be incomparable in strength.