<p>The problem of majority satisfiability <span class="math-container">$\mathsf{MAJSAT}$</span> is known to be complete for the first level <span class="math-container">$\mathsf{C_1P = PP}$</span> of the <a href="https://complexityzoo.net/Complexity_Zoo:C#ch" rel="nofollow noreferrer">Counting Hierarchy</a>  and <span class="math-container">$\mathsf{MAJMAJSAT}$</span> is known to be complete for the second level <span class="math-container">$\mathsf{C_2P = {PP}^{\mathsf{PP}}}$</span>. These languages and further extensions can be defined inductively as follows:
<span class="math-container">$$
\begin{align*}
    \mathsf{MAJSAT} &amp; = \{ \varphi(x_1) \mid \varphi(a_1) \text{ is true for } \geq\frac{1}{2} \text{ of assignments } a_1 \text{ to } x_1 \} \\
    \mathsf{{MAJ}^{2}SAT} &amp; = \{ \varphi(x_1, x_2) \mid \varphi(x_1, a_2) \in \mathsf{MAJSAT} \text{ for } \geq\frac{1}{2} \text{ of assignments } a_2 \text{ to } x_2 \} \\
    \mathsf{{MAJ}^{3}SAT} &amp; = \{ \varphi(x_1, x_2, x_3) \mid \varphi(x_1, x_2, a_3) \in \mathsf{{MAJ}^2SAT} \text{ for } \geq\frac{1}{2} \text{ of assignments } a_3 \text{ to } x_3 \} \\
    &amp; \:\:\vdots \\
    \mathsf{{MAJ}^{k}SAT} &amp; = \{ \varphi(x_1, \dots, x_k) \mid \varphi(x, \dots, x_{k-1}, a_k) \in \mathsf{{MAJ}^{k-1}SAT} \text{ for } \geq\frac{1}{2} \text{ of assignments } a_k \text{ to } x_k \} \\
\end{align*}
$$</span></p>
<p>Notice that <span class="math-container">$x_1, x_2, \dots, x_k$</span> can correspond to single variables or sets of variables as long as they are pair-wise disjoint, and notice also that <span class="math-container">$\mathsf{MAJMAJSAT} = \mathsf{{MAJ}^2SAT}$</span>.</p>
<p>Is <span class="math-container">$\mathsf{{MAJ}^3SAT}$</span> a complete problem for the third level <span class="math-container">$\mathsf{C_3P = {PP}^{({PP}^{PP})}}$</span>?</p>
<p>Furthermore, is there a generalization of these results for higher levels of the Counting Hierarchy? i.e. for every <span class="math-container">$k &gt; 0$</span>, is <span class="math-container">$\mathsf{{MAJ}^kSAT}$</span> a complete problem for the <span class="math-container">$k$</span>-th level <span class="math-container">$\mathsf{C_kP}$</span>?</p>

CC BY-SA 4.0
2024-12-17T09:13:10.153Z
Please make your question self-contained by including definitions of the problems you are asking about, in this case in particular define the problems $\textsf{MAJ}^k\textsf{SAT}$.
Jan Johannsen
CC BY-SA 4.0
2024-12-18T14:48:16.367Z
Thank you for the feedback. I edited the post to include an inductive definition of the problems :)
Benjamín Álvarez Stevenson
<cc.complexity-theory><complexity-classes><counting-complexity><generalizations>
Generalization of $\mathsf{MAJSAT}$ to higher levels of the Counting Hierarchy
Benjamín Álvarez Stevenson
# Generalization of $\mathsf{MAJSAT}$ to higher levels of the Counting Hierarchy

(Asked by: username_0 on 2024-12-16)

The problem of majority satisfiability $\mathsf{MAJSAT}$ is known to be complete for the first level $\mathsf{C\_1P = PP}$ of the [Counting Hierarchy](https://complexityzoo.net/Complexity_Zoo:C#ch) and $\mathsf{MAJMAJSAT}$ is known to be complete for the second level $\mathsf{C\_2P = {PP}^{\mathsf{PP}}}$. These languages and further extensions can be defined inductively as follows:
$$
\begin{align\*}
\mathsf{MAJSAT} & = \{ \varphi(x\_1) \mid \varphi(a\_1) \text{ is true for } \geq\frac{1}{2} \text{ of assignments } a\_1 \text{ to } x\_1 \} \\
\mathsf{{MAJ}^{2}SAT} & = \{ \varphi(x\_1, x\_2) \mid \varphi(x\_1, a\_2) \in \mathsf{MAJSAT} \text{ for } \geq\frac{1}{2} \text{ of assignments } a\_2 \text{ to } x\_2 \} \\
\mathsf{{MAJ}^{3}SAT} & = \{ \varphi(x\_1, x\_2, x\_3) \mid \varphi(x\_1, x\_2, a\_3) \in \mathsf{{MAJ}^2SAT} \text{ for } \geq\frac{1}{2} \text{ of assignments } a\_3 \text{ to } x\_3 \} \\
& \:\:\vdots \\
\mathsf{{MAJ}^{k}SAT} & = \{ \varphi(x\_1, \dots, x\_k) \mid \varphi(x, \dots, x\_{k-1}, a\_k) \in \mathsf{{MAJ}^{k-1}SAT} \text{ for } \geq\frac{1}{2} \text{ of assignments } a\_k \text{ to } x\_k \} \\
\end{align\*}
$$

Notice that $x\_1, x\_2, \dots, x\_k$ can correspond to single variables or sets of variables as long as they are pair-wise disjoint, and notice also that $\mathsf{MAJMAJSAT} = \mathsf{{MAJ}^2SAT}$.

Is $\mathsf{{MAJ}^3SAT}$ a complete problem for the third level $\mathsf{C\_3P = {PP}^{({PP}^{PP})}}$?

Furthermore, is there a generalization of these results for higher levels of the Counting Hierarchy? i.e. for every $k > 0$, is $\mathsf{{MAJ}^kSAT}$ a complete problem for the $k$-th level $\mathsf{C\_kP}$?

**Tags:** cc.complexity-theory, complexity-classes, counting-complexity, generalizations
> **Comments:**
> **username_1**: Please make your question self-contained by including definitions of the problems you are asking about, in this case in particular define the problems $\textsf{MAJ}^k\textsf{SAT}$.  
> **username_0**: Thank you for the feedback. I edited the post to include an inductive definition of the problems :)  

---

## 0 answers

