# A Compendium of Parameterized Problems at Higher Levels of the Polynomial Hierarchy
## 3 Propositional Logic Problems
### Weighted Quantified Boolean Satisfiability in the \(*\)-\(k\) Hierarchy  
Let \(d\geq 2\) be an arbitrary constant. Then, the following problem is also \(\Sigma^{\mathrm{P}}_{2}[*k,1]\)-complete.  
\(\Sigma^{\mathrm{P}}_{2}[*k]\)-\(\mathrm{WSat}(d\)-\(\mathrm{DNF})\)  
_Instance:_ A quantified Boolean formula \(\varphi=\exists X.\forall Y.\psi\) with \(\psi\in d\)-DNF, and an integer \(k\)  
_Parameter:_\(k\).  
_Question:_ Does there exist an assignment \(\alpha\) to \(X\), such that for all assignments \(\beta\) to \(Y\) of weight \(k\) the assignment \(\alpha\cup\beta\) satisfies \(\psi\)?  
**Complexity:**\(\Sigma^{\mathrm{P}}_{2}[*k,1]\)-complete for any \(d\geq 2\)[7; 8].  
The problem \(\Sigma^{\mathrm{P}}_{2}[*k]\)-\(\mathrm{WSat}(2\)-\(\mathrm{DNF})\) is \(\Sigma^{\mathrm{P}}_{2}[*k,1]\)-hard, even when we restrict the input formula to be anti-monotone in the universal variables, i.e., the universal variables occur only in negative literals [7; 8].  
Let \(C\) be a Boolean circuit with input nodes \(Z\) that is in negation normal form, and let \(Y\subseteq Z\) be a subset of the input nodes. We say that \(C\) is _monotone in \(Y\)_ if the only negation nodes that occur in the circuit \(C\) act on input nodes in \(Z\backslash Y\), i.e., input nodes in \(Y\) can appear only positively in the circuit. Similarly, we say that \(C\) is _anti-monotone in \(Y\)_ if the only nodes that have nodes in \(Y\) as input are negation nodes, i.e., all input nodes in \(Y\) appear only negatively in the circuit. The following problems are \(\Sigma^{\mathrm{P}}_{2}[*k,P]\)-complete.  
\(\Sigma^{\mathrm{P}}_{2}[*k]\)-\(\mathrm{WSat}(\forall\text{-monotone})\)  
_Instance:_ A Boolean circuit \(C\in\textsc{circ}\textsc{circ}\textsc{circ}\) over two disjoint sets \(X\) and \(Y\) of variables that is in negation normal form and that is monotone in \(Y\), and an integer \(k\).  
_Parameter:_\(k\).  
_Question:_ Does there exist a truth assignment \(\alpha\) to \(X\), such that for all truth assignments \(\beta\) to \(Y\) of weight \(k\) the assignment \(\alpha\cup\beta\) satisfies \(C\)?  
**Complexity:**\(\Sigma^{\mathrm{P}}_{2}[*k,P]\)-complete [7; 8].  
\(\Sigma^{\mathrm{P}}_{2}[*k]\)-\(\mathrm{WSat}(\forall\)-anti-monotone)  
_Instance:_ A Boolean circuit \(C\in\textsc{circ}\) over two disjoint sets \(X\) and \(Y\) of variables that is in negation normal form and that is anti-monotone in \(Y\), and an integer \(k\).  
_Parameter:_\(k\).  
_Question:_ Does there exist a truth assignment \(\alpha\) to \(X\), such that for all truth assignments \(\beta\) to \(Y\) of weight \(k\) the assignment \(\alpha\cup\beta\) satisfies \(C\)?  
**Complexity:**\(\Sigma^{\mathrm{P}}_{2}[*k,\mathrm{P}]\)-complete [7].  
It remains open what the exact parameterized complexity is of \(\exists\)-monotone and \(\exists\)-anti-monotone variants of \(\Sigma^{\mathrm{P}}_{2}[*k]\)-\(\mathrm{WSat}\)--i.e., variants of \(\Sigma^{\mathrm{P}}_{2}[*k]\)-\(\mathrm{WSat}\) that are based on circuits \(C\in\textsc{circ}\) over two disjoint sets \(X\) and \(Y\) of variables that are in negation normal form and that are (anti-)monotone in \(X\). The proofs used to show \(\Sigma^{\mathrm{P}}_{2}[*k,\mathrm{P}]\)-completeness of the \(\forall\)-monotone and \(\forall\)-anti-monotone variants [7, 8] do not immediately carry over to this case.