Answer: \(\mathrm{NP}\)-hard, even for \(\tau=2\), masses \(3/4\) and \(1/4\), and \(|S|=1\); no algorithm polynomial in \(m,\tau,L\) exists unless \(\mathrm{P}=\mathrm{NP}\).
Theorem 3 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateWINDET⋆(Approval) is Θp 2-complete.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given \(\tau\) consistent propositional goals \(\gamma_t\) over \(m\) Boolean issues with binary-rational masses \(\mu_t>0\) summing to \(1\), a set of issues \(S\), and a partial assignment \(\rho:S\to\{0,1\}\), is there a configuration \(v\) agreeing with \(\rho\) that maximizes \(\sum_{t:v\models\gamma_t}\mu_t\) over all configurations satisfying at least one supported goal?
A society is given by its support: a list of \(\tau\geq 1\) goal types \(\gamma_t\), each with positive binary-rational mass \(\mu_t\), where \(\sum_{t=1}^{\tau}\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types.
Each goal is a satisfiable propositional formula, given explicitly using \(\land,\lor,\neg,\to\), over \(m\geq1\) Boolean issues \(I=\{1,\ldots,m\}\). All configurations \(v\in\{0,1\}^m\) are feasible; there are no integrity constraints.
Define \(D=\{v:\exists t,\ v\models\gamma_t\}\), \(a(v)=\sum_{t:v\models\gamma_t}\mu_t\), and \(W=\operatorname*{arg\,max}_{v\in D}a(v)\); every tied maximizer belongs to \(W\).
The input also contains \(S\subseteq I\) and \(\rho:S\to\{0,1\}\). Decide whether some \(v\in W\) satisfies \(v|_S=\rho\); maximization is global, before imposing \(\rho\).
Let \(L\) be the total binary input length, including formulas, masses, and the partial assignment. State running times in \(m,\tau,L\).
Is this decision problem solvable in polynomial time in \(m,\tau,L\), or is it NP-hard?
For a finite list of equally weighted agents with satisfiable propositional goals, deciding whether a global approval maximizer extends a given partial assignment is \(\Theta_2^p\)-complete. [Source](https://www.ijcai.org/proceedings/2018/0065.pdf)
No result settling exactly the support-encoded rational-mass version was identified in the literature search.
The problem is \(\mathrm{NP}\)-hard, even with support size \(\tau=2\), fixed dyadic masses, and a partial assignment prescribing just one issue. Consequently, it has no algorithm polynomial in \(m,\tau,L\) unless \(\mathrm{P}=\mathrm{NP}\).
Already \(\tau=1\) is hard: for a SAT instance \(\varphi\), the satisfiable goal \(z\lor\varphi\), with a fresh issue \(z\), has a winner extending \(z=0\) exactly when \(\varphi\) is satisfiable. The following reduction additionally makes global maximization select between different approval scores.
We use the standard fact that satisfiability of explicitly represented propositional CNF formulas is \(\mathrm{NP}\)-complete.
Let \(\varphi\) be such a formula over issues \(x_1,\ldots,x_n\). Introduce a fresh issue \(z\), and construct the society
\(\displaystyle \gamma_1=\neg z\lor\varphi,\qquad \mu_1=\frac34,\qquad \gamma_2=z,\qquad \mu_2=\frac14.\)
Set \(S=\{z\}\) and \(\rho(z)=1\).
Validity of the constructed instance.
The approval score is determined exactly by the following table.
| Configuration condition | Satisfied goals | Approval score |
|---|---|---|
| \(z=0\) | \(\gamma_1\) only | \(3/4\) |
| \(z=1\) and \(\varphi\) true | Both goals | \(1\) |
| \(z=1\) and \(\varphi\) false | \(\gamma_2\) only | \(1/4\) |
We now prove both directions.
If \(\varphi\) is satisfiable, extend any satisfying assignment by \(z=1\). Its score is \(1\), the largest possible score because the total mass is \(1\). It therefore belongs to \(W\) and extends \(\rho\). In fact,
\(\displaystyle W=\{v:v(z)=1\text{ and }v\models\varphi\}.\)
If \(\varphi\) is unsatisfiable, every configuration with \(z=1\) has score \(1/4\), whereas every configuration with \(z=0\) has score \(3/4\). Hence
\(\displaystyle W=\{v:v(z)=0\},\)
so no winner extends \(\rho\).
Consequently,
\(\displaystyle \varphi\text{ is satisfiable}\quad\Longleftrightarrow\quad \exists v\in W\text{ with }v|_S=\rho.\)
This is a polynomial-time many-one reduction from SAT. It proves hardness while retaining all tied global maximizers and performing maximization before imposing the partial assignment.
The rational masses also admit a direct algorithm without expanding the society into individual agents.
Write each mass as \(\mu_t=p_t/q_t\), where \(p_t,q_t\) are positive binary-encoded integers. Define
\(\displaystyle Q=\prod_{t=1}^{\tau}q_t,\qquad w_t=p_t\frac{Q}{q_t},\qquad A(v)=\sum_{t:v\models\gamma_t}w_t.\)
Each \(w_t\) is an integer, and
\(\displaystyle \sum_{t=1}^{\tau}w_t=Q,\qquad a(v)=A(v)/Q.\)
The binary length of \(Q\) is at most one plus the sum of the binary lengths of the denominators, hence is \(O(L)\). Moreover, \(0<w_t\le Q\). Thus all these integers can be computed and manipulated in polynomial time in \(L\).
Because at least one goal is satisfiable and every mass is positive, some configuration has positive score. Configurations outside \(D\) have score zero. Therefore maximizing \(A\) over all configurations gives exactly the original winner set \(W\).
Enumerate all configurations, compute their integer scores, and maintain:
The two maxima are equal exactly when the answer is yes. Formula evaluation and integer arithmetic take polynomial time per configuration, giving running time
\(\displaystyle O\!\left(2^m\operatorname{poly}(m,\tau,L)\right).\)
More precisely, only issues occurring in a goal or in \(S\) need to be enumerated. If their number is \(r\), then \(r\le m\) and \(r=O(L)\), and the running time is
\(\displaystyle O\!\left(2^r\operatorname{poly}(L)\right).\)
Assignments to these issues extend arbitrarily to unused issues without changing any score or prescribed value.
For an integer threshold \(k\), consider the question
\(\displaystyle \exists v\in\{0,1\}^{m}\quad A(v)\ge k.\)
This predicate belongs to \(\mathrm{NP}\): a certificate specifies the relevant issue values, and the formulas and integer score can be checked in polynomial time.
Binary search on the integer interval from \(0\) to \(Q\) finds the global maximum \(M\) using \(O(\log(Q+1))=O(L)\) oracle queries. One additional query asks
\(\displaystyle \exists v\quad v|_S=\rho\text{ and }A(v)\ge M.\)
Since \(M\) is the global maximum, this query is equivalent to the required winner-extension question. Thus the problem belongs to \(\mathrm{P}^{\mathrm{NP}}\), with \(O(L)\) NP-oracle calls and polynomial overhead in \(m,\tau,L\).
The supplied [IJCAI paper, Theorem 3](https://www.ijcai.org/proceedings/2018/0065.pdf), establishes \(\Theta_2^p\)-completeness for explicitly listed equally weighted agents. The reduction above directly settles the requested polynomial-time-versus-hardness question for support-encoded masses, including dyadic masses.
In particular, a constant support size does not guarantee tractability: the formulas themselves retain SAT hardness.
⟨structured verdict parsed — rendered above⟩
The prover’s output is correct and resolves the requested complexity question. The reduction establishes \(\mathrm{NP}\)-hardness under all the input promises, even with \(\tau=2\), fixed dyadic masses, and one prescribed issue. The enumeration and oracle upper bounds are also valid. No major or minor mathematical issues were found.
The stated source problem—satisfiability of explicitly represented propositional CNF formulas—is \(\mathrm{NP}\)-complete. The reduction accepts arbitrary such formulas; it does not assume that the source formula \(\varphi\) is satisfiable.
Introducing a fresh issue \(z\) and forming \(\gamma_1=\neg z\lor\varphi\) and \(\gamma_2=z\) requires only one copy of \(\varphi\) and constant additional formula structure. The masses and partial assignment have constant size apart from issue identifiers. Thus the construction takes polynomial time and produces polynomial output length. Its issue count is \(m=n+1\), so the required condition \(m\geq1\) holds.
Both constructed goals are satisfiable regardless of whether \(\varphi\) is satisfiable:
The masses \(\mu_1=3/4\) and \(\mu_2=1/4\) are positive binary rationals summing to one. The two goals are semantically distinct because every assignment with \(z=0\) satisfies the first and falsifies the second.
Every configuration satisfies at least one goal, so the claimed identity \(D=\{0,1\}^{n+1}\) is correct. No integrity constraint or additional feasibility assumption enters the construction.
Each row of the table is correct:
These cases exhaust all configurations. The strict inequalities \(1>3/4>1/4\) justify the subsequent winner-set descriptions.
If \(\varphi\) is satisfiable, the configurations satisfying \(z=1\) and \(\varphi\) attain score \(1\). No larger score is possible because the total mass is one. Every other configuration has strictly smaller score. Therefore the stated winner set is exact, and a winner extends \(\rho(z)=1\).
If \(\varphi\) is unsatisfiable, all configurations with \(z=1\) have score \(1/4\), while all configurations with \(z=0\) have score \(3/4\). Thus precisely the latter configurations are winners, and none extends \(\rho\).
Consequently, the displayed equivalence is valid and gives a polynomial-time many-one reduction. All tied maximizers are retained, and maximization occurs globally before checking the partial assignment. The implication excluding polynomial time unless \(\mathrm{P}=\mathrm{NP}\) follows.
The introductory \(\tau=1\) construction is also correct. Normalization forces the sole mass to be one. The goal \(z\lor\varphi\) is always satisfiable, and every configuration satisfying that goal is a winner. Such a winner has \(z=0\) exactly when its remaining values satisfy \(\varphi\). This establishes the claimed equivalence without violating the satisfiability promise.
For the stated representation \(\mu_t=p_t/q_t\), the product \(Q=\prod_t q_t\) is divisible by each denominator, so every \(w_t=p_t(Q/q_t)\) is an integer. Normalization gives \(\sum_t w_t=Q\), and therefore \(a(v)=A(v)/Q\).
The binary length of \(Q\) is bounded by one plus the sum of denominator bit lengths, hence is \(O(L)\). Positivity and the sum identity imply \(0<w_t\leq Q\). The arithmetic therefore uses polynomially many bits and polynomial time.
At least one satisfiable goal has positive mass, so the global maximum is positive. Configurations outside \(D\) have score zero and cannot maximize. Thus maximizing over all configurations yields exactly the original \(W\).
The enumeration algorithm correctly compares the global maximum with the maximum among extensions of \(\rho\). The latter set is nonempty because every partial assignment on \(S\) extends to a feasible configuration. Equality of these maxima is precisely the requested existential condition.
Formula evaluation and score arithmetic have polynomial cost per configuration, validating \(O(2^m\operatorname{poly}(m,\tau,L))\). Enumerating only the \(r\) issues appearing in goals or \(S\) is valid: unused issues affect neither scores nor prescribed values. Explicit input representation gives \(r=O(L)\), validating the refined bound.
The threshold predicate belongs to \(\mathrm{NP}\): values for the relevant issues form a polynomial-size certificate, and their score is polynomial-time checkable. Binary search over the integer range from zero through \(Q\) needs \(O(\log(Q+1))=O(L)\) queries. The final constrained threshold query at the global maximum is equivalent to winner extension. The claimed \(\mathrm{P}^{\mathrm{NP}}\) upper bound follows.
The cited paper defines the existential partial-assignment winner question and states its \(\Theta_2^p\)-completeness for Approval in Theorem 3, with satisfiable propositional goals and all interpretations feasible. The attribution is accurate. [IJCAI paper, Sections 2.1 and 4](https://www.ijcai.org/proceedings/2018/0065.pdf)
The prover does not claim that this completeness classification transfers unchanged to arbitrary rational masses. Its independent reduction settles the requested hardness question, and its independently justified oracle algorithm supplies an upper bound.
Actionable feedback: No mathematical repair or additional clarification is required.
⟨structured verdict parsed — rendered above⟩
Tier: machine-proved, adversarially reviewed by an independent model. No human has checked this proof. Generated from pipeline artifacts by tools/atlas_build.py.