Answer: —
Proposition 1 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateEquations (7-9) where Lt is replaced by ˜Lt admit closed-form solutions given in Algorithm 2 line 7-9. The proof is given in the supplementary material. The re- sulting online learning process is given in Algorithm 2 and its benefit for retrieving monotonic capacity is illustrated in the next section with numerical experiments.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite menu of alternatives in \([0,1]^n\), a fixed local aggregator \(\phi\), and a rational distribution \(\mu\) over report types \(t=(x_t,y_t,r_t)\), where \(r_t\) records strict preference or indifference, find a normalized Möbius vector \(m\) minimizing \(\sum_t \mu_t\ell_t(m)+\lambda\|m\|_1\), subject to monotonicity of \(v(S)=\sum_{R\subseteq S}m(R)\), optionally with supermodularity. Here \(\ell_t(m)=[\delta-\langle m,\phi(x_t)-\phi(y_t)\rangle]_+\) for strict preference and \(\ell_t(m)=[|\langle m,\phi(x_t)-\phi(y_t)\rangle|-\delta]_+\) for indifference.
Let \(N=\{1,\ldots,n\}\), with \(n\geq1\), and let \(X\subseteq[0,1]^n\) be an explicitly listed menu of \(m\geq2\) rational alternatives. Fix a family of local aggregators \(\phi_S\), uniformly evaluable exactly in polynomial time on rational inputs, with rational outputs and \(\phi_{\{i\}}(x_i)=x_i\); set \(\phi_\varnothing=0\).
A society is given by its support: the list of the \(\tau\) report types \(t=(x_t,y_t,r_t)\) with positive binary-rational masses \(\mu_t\), summing to \(1\). Here \(x_t,y_t\in X\) are distinct, and \(r_t\) records either \(x_t\succ y_t\) or \(x_t\sim y_t\). The parameter \(\tau\) is the support size, not the number of possible types.
The variables are signed real Möbius coefficients \(\boldsymbol m=(m(S))_{S\subseteq N}\), with \(m(\varnothing)=0\) and \(\sum_{S\subseteq N}m(S)=1\). Define \(v(S)=\sum_{R\subseteq S}m(R)\), and require \(v(A)\leq v(B)\) whenever \(A\subseteq B\). There is no restriction on interaction order or number of nonzero coefficients.
A binary input flag additionally requires supermodularity when enabled: \(v(A\cup B)+v(A\cap B)\geq v(A)+v(B)\) for all \(A,B\subseteq N\).
Given positive binary-rational \(\delta,\lambda\), put \(d_t=\sum_{S\subseteq N}m(S)(\phi_S((x_t)_S)-\phi_S((y_t)_S))\). Define \(\ell_t=[\delta-d_t]_+\) for strict reports and \(\ell_t=[|d_t|-\delta]_+\) for indifference reports, where \([z]_+=\max\{z,0\}\).
The objective is \(J(\boldsymbol m)=\sum_t\mu_t\ell_t+\lambda\sum_{S\subseteq N}|m(S)|\). Given a binary-rational threshold \(q\), decide whether an admissible \(\boldsymbol m\) has \(J(\boldsymbol m)\leq q\). The subset-indexed coefficients and constraints are implicit; \(L\) is the total input bit length.
For each fixed aggregator family, is this decision problem in \(\mathrm P\) or NP-hard, with and without the supermodularity requirement? State running times in \(n,m,\tau,L\).
For finite report sequences, closed-form updates are known for a linearized ADMM–RDA procedure; this does not establish exact batch optimization in polynomial time in \(n\). Explicit batch formulations are treated by linear programming with exponentially many subset-indexed coefficients. [Source](https://www.ijcai.org/proceedings/2024/0787.pdf)
No verified result here settles the stated implicitly represented, rational-mass decision problem.
The stated assumptions do not support a universal $\mathrm P$/NP-hard dichotomy unless $\mathrm P=\mathrm{NP}$.
I prove the following stronger limitation:
There is a fixed aggregator family satisfying all the stated requirements such that, if $\mathrm P\ne\mathrm{NP}$, its decision problem is neither in $\mathrm P$ nor NP-hard, with either setting of the supermodularity flag.
Here NP-hardness means hardness under polynomial-time many-one reductions. No membership in $\mathrm{NP}$ is claimed for this constructed family.
Consequently, the assertion that every permitted fixed aggregator family yields a problem in $\mathrm P$ or an NP-hard problem is equivalent to $\mathrm P=\mathrm{NP}$. This addresses the missing universal scope in the notes, although the unconditional truth of that assertion remains open.
The unconditional classifications from the notes also hold:
| Fixed family for nonempty $S$ | Without supermodularity | With supermodularity |
|---|---|---|
| $\phi_S(z_S)=|S|^{-1}\sum_{i\in S}z_i$ | $\mathrm P$ | $\mathrm P$ |
| $\phi_S(z_S)=z_{\max S}$ | $\mathrm P$ | $\mathrm P$ |
| $\phi_S(z_S)=\min_{i\in S}z_i$ | NP-hard | NP-hard |
| $\phi_S(z_S)=\prod_{i\in S}z_i$ | NP-hard | NP-hard |
Every permitted fixed family admits an exact algorithm in
$$
2^{O(n)}\operatorname{poly}_{\phi}(n,m,\tau,L)
$$
bit operations. The two polynomial cases above run in
$$
\operatorname{poly}(n,m,\tau,L).
$$
All these statements are proved below. For $n=1$, normalization forces $m(\{1\})=1$, so the decision is immediately computable; the complexity questions concern unbounded $n$.
For each report and subset, define
$$
b_t(S)=\phi_S((x_t)_S)-\phi_S((y_t)_S).
$$
Introduce rational LP variables $m(S),v(S),z(S)$ for every subset, and $h_t$ for every report. Require
$$
m(\varnothing)=v(\varnothing)=0,\qquad
v(S)=\sum_{R\subseteq S}m(R),\qquad
v(N)=1,
$$
and
$$
z(S)\geq m(S),\qquad z(S)\geq-m(S).
$$
Monotonicity is imposed through the cover inequalities
$$
v(A\cup\{i\})\geq v(A)
\qquad(i\notin A).
$$
They imply every required inclusion inequality by adding the missing elements successively.
When enabled, supermodularity is imposed through
$$
v(A\cup\{i,j\})+v(A)
\geq v(A\cup\{i\})+v(A\cup\{j\})
\qquad(i\ne j,\ i,j\notin A).
$$
These inequalities are equivalent to full supermodularity. Indeed, they state that
$$
\Delta_i(A)=v(A\cup\{i\})-v(A)
$$
cannot decrease when another element is added to $A$. Iteration gives
$$
\Delta_i(A)\leq\Delta_i(B)
\qquad(A\subseteq B,\ i\notin B).
$$
For arbitrary $C,D$, add the elements of $C\setminus D$ in the same order, first starting from $C\cap D$ and then starting from $D$. At every addition the former current set is contained in the latter. Summing the marginal comparisons gives
$$
v(C)-v(C\cap D)\leq v(C\cup D)-v(D).
$$
Necessity follows by using $C=A\cup\{i\}$ and $D=A\cup\{j\}$.
For a strict report, impose
$$
h_t\geq0,\qquad
h_t\geq\delta-\sum_S b_t(S)m(S).
$$
For an indifference report, impose
$$
h_t\geq0,\qquad
h_t\geq\sum_S b_t(S)m(S)-\delta,\qquad
h_t\geq-\sum_S b_t(S)m(S)-\delta.
$$
Finally, impose
$$
\sum_t\mu_t h_t+\lambda\sum_S z(S)\leq q.
$$
This LP is feasible exactly when the original instance is a yes-instance. Its inequalities imply $h_t\geq\ell_t$ and $z(S)\geq|m(S)|$; conversely, an original feasible vector extends by assigning these quantities their exact values.
There are $O(2^n+\tau)$ variables and $O(n^2 2^n+\tau)$ constraints. The subset-sum equations contain
$$
\sum_{S\subseteq N}2^{|S|}=3^n
$$
coefficient occurrences. Uniform polynomial-time exact evaluation bounds both evaluation time and rational output length by a fixed polynomial in the input size. The explicit LP therefore has encoding length
$$
2^{O(n)}\operatorname{poly}_{\phi}(n,m,\tau,L).
$$
Polynomial-time feasibility of explicitly represented rational LPs proves the claimed running time.
This also supplies a terminating exact decision procedure needed later in the diagonalization.
Suppose
$$
\phi_S(z_S)=\frac1{|S|}\sum_{i\in S}z_i
\qquad(S\ne\varnothing).
$$
For an admissible vector, define
$$
a_i=\sum_{S\ni i}\frac{m(S)}{|S|}.
$$
Interchanging finite sums gives
$$
F_{\boldsymbol m}(x)
=\sum_Sm(S)\phi_S(x_S)
=\sum_i a_i x_i.
$$
To prove $a_i\geq0$, choose a uniformly random permutation $\pi$ of $N$, and let $P_i^\pi$ be the predecessors of $i$. Expanding a capacity marginal gives
$$
v(P_i^\pi\cup\{i\})-v(P_i^\pi)
=
\sum_{\substack{S\ni i\\S\setminus\{i\}\subseteq P_i^\pi}}m(S).
$$
For fixed $S\ni i$, the condition in this sum holds precisely when $i$ is last among the elements of $S$, an event of probability $1/|S|$. Thus
$$
a_i
=
\mathbb E_\pi\bigl[v(P_i^\pi\cup\{i\})-v(P_i^\pi)\bigr]
\geq0.
$$
The inequality uses monotonicity; linearity of expectation remains valid for signed coefficients. Also,
$$
\sum_i a_i=\sum_{S\ne\varnothing}m(S)=1.
$$
Replace the original vector by
$$
m'(\{i\})=a_i,\qquad m'(S)=0\quad(|S|\ne1).
$$
Its capacity is additive, hence monotone and supermodular. It preserves every score, and
$$
\|\boldsymbol m'\|_1=1
\leq\|\boldsymbol m\|_1,
$$
where the inequality follows from normalization.
The optimum therefore equals
$$
\lambda+
\min_{\substack{a_i\geq0\\\sum_i a_i=1}}
\sum_t\mu_t\,
\ell_t\!\left(\sum_i a_i((x_t)_i-(y_t)_i)\right).
$$
The loss epigraph inequalities from Section 1 give an LP with $n+\tau$ variables and $O(n+\tau)$ constraints, of polynomial encoding length. This proves polynomial-time solvability under either flag, for arbitrary allowed losses and parameters.
Let
$$
g:\mathbb N_{\geq1}\longrightarrow\{0,1\}
$$
be a fixed function computable in polynomial time from the binary representation of its argument. Define
$$
\phi^g_\varnothing=0,
$$
and, for nonempty $S$,
$$
\phi^g_S(z_S)=
\begin{cases}
\min_{i\in S}z_i,&g(\max S)=1,\\
z_{\max S},&g(\max S)=0.
\end{cases}
$$
These are local aggregators: they use only the coordinates indexed by $S$. Dependence on the labels in $S$ is permitted by the task, which imposes no symmetry requirement. Both branches agree on singletons, have rational outputs, and are exactly evaluable in polynomial time.
Write $D_{g,b}$ for the decision language with this family and flag fixed to $b\in\{0,1\}$. Fix an ordinary explicit binary encoding, and reject malformed inputs. Validity of the input format is polynomial-time checkable.
The next two lemmas establish the contrasting behavior of the two possible constant tails of $g$.
Lemma. If $g(r)=0$ for all $r>K$, where $K$ is a fixed constant, then both $D_{g,0}$ and $D_{g,1}$ are in $\mathrm P$. More explicitly, they are solvable in
$$
2^{O(K)}\operatorname{poly}_g(n,m,\tau,L)
$$
bit operations.
Proof. Put
$$
H=\{1,\ldots,\min(K,n)\}.
$$
For every $i>K$, define
$$
a_i=\sum_{\max R=i}m(R).
$$
The sets counted by this sum are exactly the subsets of $\{1,\ldots,i\}$ that are not subsets of $\{1,\ldots,i-1\}$. Therefore
$$
a_i=v(\{1,\ldots,i\})-v(\{1,\ldots,i-1\})\geq0.
$$
Retain every coefficient indexed by a subset of $H$, replace all coefficients having maximum $i>K$ by the single coefficient $m'(\{i\})=a_i$, and set the other coefficients to zero. The new capacity is
$$
v'(A)=v(A\cap H)+\sum_{\substack{i\in A\\i>K}}a_i.
$$
It is monotone. If the original capacity is supermodular, its restriction to $H$ is supermodular, and the displayed additive extension is supermodular as well.
Telescoping gives
$$
v(H)+\sum_{i>K}a_i=v(N)=1,
$$
so normalization is preserved.
For every $R$ with $\max R=i>K$, the aggregator is $x_i$. Hence the original score is
$$
F_{\boldsymbol m}(x)
=
\sum_{\varnothing\ne R\subseteq H}m(R)\phi^g_R(x_R)
+\sum_{i>K}a_i x_i,
$$
which is exactly the replacement score. Finally,
$$
\|\boldsymbol m'\|_1
=
\sum_{R\subseteq H}|m(R)|+\sum_{i>K}a_i
\leq
\sum_{R\subseteq H}|m(R)|
+\sum_{i>K}\sum_{\max R=i}|m(R)|
=
\|\boldsymbol m\|_1.
$$
Thus the replacement cannot increase the objective.
Conversely, every monotone capacity on $H$, with nonnegative outside weights satisfying
$$
v(H)+\sum_{i>K}a_i=1,
$$
defines an admissible capacity through the displayed extension. The same equivalence holds with supermodularity required.
Consequently, it suffices to use the subset variables on $H$, the $n-|H|$ outside weights, and the report epigraph variables. The LP construction of Section 1 now has encoding length
$$
2^{O(K)}\operatorname{poly}_g(n,m,\tau,L).
$$
Rational LP feasibility proves the lemma. $\square$
Taking $g\equiv0$ gives the coordinate-projection classification in the opening table.
Lemma. Suppose all aggregator values on the menu belong to $[0,1]$, and $\lambda\geq1$. Every admissible signed vector can be replaced, without increasing its objective, by a nonnegative normalized Möbius vector. The replacement satisfies both monotonicity and supermodularity.
Proof. Let
$$
\eta=\sum_S[-m(S)]_+.
$$
Normalization implies that the positive mass is $1+\eta$ and
$$
\|\boldsymbol m\|_1=1+2\eta.
$$
Define
$$
p(S)=\frac{[m(S)]_+}{1+\eta}.
$$
Then $p(\varnothing)=0$, all its coefficients are nonnegative, and their sum is $1$. Removing negative mass changes the vector by $\eta$ in absolute sum, and renormalizing its positive part changes it by another $\eta$. Thus
$$
\|\boldsymbol p-\boldsymbol m\|_1=2\eta.
$$
The range assumption gives $|b_t(S)|\leq1$, so
$$
|d_t(\boldsymbol p)-d_t(\boldsymbol m)|\leq2\eta.
$$
Both specified loss functions are $1$-Lipschitz. Since the masses sum to $1$, the total weighted loss increases by at most $2\eta$. The regularizer decreases by $2\lambda\eta$, giving
$$
J(\boldsymbol p)\leq J(\boldsymbol m)+2\eta(1-\lambda)
\leq J(\boldsymbol m).
$$
For a nonempty $R$, define the unanimity capacity
$$
u_R(A)=\mathbf1\{R\subseteq A\}.
$$
It is monotone and supermodular. For the latter property, if $R$ is contained in both arguments, both sides of the supermodular inequality equal $2$; if in exactly one, both sides equal $1$; if in neither, the right side is zero and the left side is nonnegative.
The replacement capacity is
$$
v_{\boldsymbol p}(A)=\sum_Rp(R)u_R(A).
$$
A nonnegative combination preserves both properties, and the required normalization follows from $\sum_Rp(R)=1$. $\square$
Lemma. If $g(r)=1$ for all $r>K$, where $K$ is fixed, then $D_{g,b}$ is NP-hard for each $b$.
Proof. Reduce from Independent Set on a simple graph with $p$ vertices and threshold $k$, restricted to $p\geq2$ and $1\leq k\leq p$. This restricted problem is NP-hard: the usual reduction from $3$-SAT uses one vertex for each literal occurrence, clause cliques, and edges between complementary occurrences. An independent set of size equal to the number of clauses exists precisely when the formula is satisfiable.
Add $h=K+1$ isolated vertices, placing them after the original vertices in the labeling. Call the resulting graph $G=(N,E)$ and set $n=p+h$. Then
$$
\alpha(G)=\alpha(G_{\mathrm{original}})+h,
$$
and vertex $n$ is isolated. Every maximum independent set includes $n$, since otherwise it could be enlarged.
Let $\boldsymbol1$ be the all-ones alternative. For each vertex $i$, let $c_i$ have its only zero at $i$. For each edge $\{i,j\}$, let $c_{ij}$ have zeros at $i,j$. Use the menu
$$
X=\{\boldsymbol1\}\cup\{c_i:i\in N\}
\cup\{c_{ij}:\{i,j\}\in E\}.
$$
All alternatives are distinct.
Put
$$
C=n+1,\qquad W=n+2C|E|,
$$
and let $D$ be the smallest power of two strictly larger than $W$. Use these strict reports:
| Report | Mass |
|---|---|
| $\boldsymbol1\succ c_i$, for each vertex $i$ | $1/D$ |
| $c_i\succ\boldsymbol1$, for each edge $\{i,j\}$ with $i<j$ | $C/D$ |
| $c_j\succ c_{ij}$, for the same edge | $C/D$ |
Add $\boldsymbol1\succ c_1$ and $c_1\succ\boldsymbol1$, each with mass
$$
\frac{D-W}{2D}.
$$
Merge repeated types by adding their masses. All resulting masses are positive dyadic rationals and sum to $1$.
Choose
$$
\delta=2,\qquad\lambda=1,\qquad
q=3-\frac{k+h}{D}.
$$
For a nonempty subset $S$, let $H(S)/D$ be the mass-weighted sum of report differences for the vector with coefficient $1$ on $S$ and zero elsewhere. The added opposite reports cancel.
If the aggregator on $S$ is minimum, put
$$
a_i=\mathbf1\{i\notin S\}.
$$
Its values on $\boldsymbol1,c_i,c_{ij}$ are respectively $1,a_i,a_i a_j$. Therefore
$$
\begin{aligned}
H(S)
&=\sum_i(1-a_i)
+C\sum_{\substack{\{i,j\}\in E\\i<j}}
(a_i-1+a_j-a_i a_j)\\
&=|S|-C\,e_G(S),
\end{aligned}
$$
where $e_G(S)$ counts edges internal to $S$. An independent $S$ has $H(S)=|S|$, while a nonindependent $S$ has
$$
H(S)\leq n-C=-1.
$$
If the aggregator on $S$ is coordinate projection, write $r=\max S$. Its vertex contributions sum to $1$. Every edge contribution vanishes because
$$
(c_i)_r-1+(c_j)_r-(c_{ij})_r=0.
$$
Thus $H(S)=1$ for a projection column.
It follows that every column satisfies $H(S)\leq\alpha(G)$. A maximum independent set contains $n>K$, so its aggregator is minimum and its column attains $\alpha(G)$. Hence
$$
\max_{\varnothing\ne S\subseteq N}H(S)=\alpha(G).
$$
The signed replacement lemma applies. For nonnegative normalized coefficients, scores lie in $[0,1]$, so every strict loss is exactly $2-d_t$ and the regularizer is $1$. Consequently,
$$
J(\boldsymbol p)
=
3-\frac1D\sum_{S\ne\varnothing}p(S)H(S).
$$
The sum is a convex combination of column values. Concentration on a maximum independent set attains its maximum; the corresponding unanimity capacity satisfies either flag. Therefore
$$
\min J=3-\frac{\alpha(G)}D.
$$
The threshold condition is equivalent to
$$
\alpha(G)\geq k+h
\quad\Longleftrightarrow\quad
\alpha(G_{\mathrm{original}})\geq k.
$$
The reduction has
$$
m=1+n+|E|=O(n^2),\qquad
\tau\leq n+2|E|+2=O(n^2),
$$
and $D\leq2W=O(n^3)$. Its total encoding length is $O(n^3)$ under the usual explicit encoding, and construction time is polynomial. The constant $K$ depends only on the fixed family. $\square$
With $g\equiv1$, no isolated-vertex padding is needed, and this proves hardness for minimum aggregators. Product aggregators have the same values on the binary menu and remain in $[0,1]$ on every allowed alternative, so exactly the same reduction and signed replacement prove their hardness.
I now construct a single fixed, polynomial-time computable gate $g$. The construction is unconditional; its complexity consequences use $\mathrm P\ne\mathrm{NP}$.
It uses delayed diagonalization, the technique underlying Ladner’s theorem. The version needed here is proved directly; it does not require assuming that these decision languages belong to $\mathrm{NP}$. See [Two Proofs of Ladner’s Theorem](https://web.cs.ucdavis.edu/~rogaway/classes/220/winter06/ladner-theorem.pdf) for the classical technique.
Effectively enumerate:
For example, enumerate pairs consisting of a machine program and a polynomial clock, truncating execution when the clock expires. Every polynomial-time decider or string function occurs in the appropriate enumeration.
For each $i$, impose four requirements:
| Phase | Requirement | Gate value while waiting |
|---|---|---|
| $4i$ | $M_i$ fails to decide $D_{g,0}$ | $1$ |
| $4i+1$ | $R_i$ fails to reduce SAT to $D_{g,0}$ | $0$ |
| $4i+2$ | $M_i$ fails to decide $D_{g,1}$ | $1$ |
| $4i+3$ | $R_i$ fails to reduce SAT to $D_{g,1}$ | $0$ |
A phase ends only after finding a finite witness to its requirement.
For a decision-machine requirement, enumerate strings $z$ and test whether
$$
M_i(z)\ne\mathbf1\{z\in D_{g,b}\}.
$$
For a reduction requirement, enumerate strings $z$ and test whether
$$
\mathbf1\{z\in\mathrm{SAT}\}
\ne
\mathbf1\{R_i(z)\in D_{g,b}\}.
$$
SAT can be decided by exhaustive search. Section 1 supplies an exact terminating procedure for the target decision.
The remaining issue is to make $g$ polynomial-time computable while these searches can take arbitrarily long.
Define bits $a_0,a_1,\ldots$, and then set
$$
g(r)=a_{\lfloor\log_2 r\rfloor}.
$$
The construction proceeds in calendar ticks $j=0,1,\ldots$. At tick $j$:
A search deciding a target instance evaluates minimum or projection using the table of assigned bits. If it requests an unassigned bit $a_s$, it pauses until calendar tick $s$ assigns that bit. This pause does not prevent later calendar ticks from assigning bits.
For a target instance of dimension $d$, all its aggregator columns use only
$$
a_0,\ldots,a_{\lfloor\log_2 d\rfloor}.
$$
Thus every target decision eventually has all the gate bits it needs. Once available, its explicit LP computation terminates.
This defines an ordinary effective construction: its background computation uses a universal machine simulator, a growing bit table, and the exact finite algorithms described above. It does not call the as-yet-undefined gate as an oracle. It reads already assigned table entries and waits for future entries when necessary.
To evaluate $g(r)$, simulate the construction only through tick
$$
j=\lfloor\log_2 r\rfloor.
$$
There are $j+1$ ticks and at most $j+1$ background transitions. The table, simulator configuration, and phase counter have polynomial size in $j+1$. Straightforward universal simulation and table access therefore take
$$
O((j+1)^c)
$$
time for some fixed constant $c$. Hence $g(r)$ is computable in polynomial time in the binary length of $r$.
It follows that $\phi^g$ is a valid uniformly polynomial-time evaluable fixed aggregator family.
Every discovered witness remains valid permanently: its target decision used only gate bits that had already been assigned, and none of those bits is subsequently changed.
Assume $\mathrm P\ne\mathrm{NP}$.
Suppose a decision-machine phase remains forever. From some calendar tick onward, all assigned bits equal $1$, so $g(r)=1$ for all sufficiently large $r$. Section 3.3 then makes the relevant $D_{g,b}$ NP-hard.
During a permanent phase, every finite candidate string is eventually examined. Its clocked machine computation terminates, every required gate bit eventually becomes available, and its exact target decision terminates. If no witness exists, $M_i$ decides $D_{g,b}$ correctly on every string. This would put an NP-hard language in $\mathrm P$, contradicting the assumption.
Now suppose a reduction phase remains forever. Its tail gate equals $0$, so Section 3.1 puts the relevant $D_{g,b}$ in $\mathrm P$. Again every finite candidate is eventually examined. If no witness exists, $R_i$ is a valid polynomial-time many-one reduction from SAT to this polynomial-time language. This would put SAT in $\mathrm P$, another contradiction.
Therefore every phase ends.
Every polynomial-time decider is consequently defeated for each flag, and every polynomial-time reduction from SAT is defeated for each flag. We obtain
$$
D_{g,0}\notin\mathrm P,\qquad D_{g,1}\notin\mathrm P,
$$
and
$$
\mathrm{SAT}\not\leq_m^p D_{g,0},\qquad
\mathrm{SAT}\not\leq_m^p D_{g,1}.
$$
Neither language is NP-hard.
This proves the promised conditional obstruction for the full decision problems, including signed coefficients, arbitrary positive rational parameters, and both kinds of reports.
Let $\mathcal D$ denote the assertion:
For every permitted fixed aggregator family, and for each flag setting, the decision problem is in $\mathrm P$ or is NP-hard.
Section 4 proves
$$
\mathcal D\Longrightarrow\mathrm P=\mathrm{NP},
$$
because otherwise its constructed family violates both alternatives for both flags.
For completeness, the converse also holds, even without proving that the decision problems belong to $\mathrm{NP}$.
Every permitted family has a fixed yes-instance and a fixed no-instance. Take $n=1$, menu $X=\{0,1\}$, one strict report $1\succ0$ of mass $1$, and
$$
\delta=\lambda=1.
$$
Normalization forces $m(\{1\})=1$. The loss is zero and the objective is $1$, so threshold $q=1$ gives a yes-instance and threshold $q=0$ gives a no-instance. The capacity is modular, so these instances work for either flag and every permitted family.
If $\mathrm P=\mathrm{NP}$, any language $A\in\mathrm{NP}$ has a polynomial-time decider. Decide whether the source input belongs to $A$, and output the fixed yes-instance or fixed no-instance accordingly. This is a polynomial-time many-one reduction from $A$ to the decision problem. Thus every permitted family’s problem is NP-hard.
Consequently,
$$
\boxed{\mathcal D\quad\Longleftrightarrow\quad\mathrm P=\mathrm{NP}.}
$$
The weak assumptions therefore permit a third complexity possibility if $\mathrm P\ne\mathrm{NP}$. Additional structural hypotheses would be needed for a meaningful universal binary classification.
The proved algorithmic bounds are:
| Setting | Exact running time |
|---|---|
| Any permitted fixed family | $2^{O(n)}\operatorname{poly}_{\phi}(n,m,\tau,L)$ |
| Arithmetic mean | $\operatorname{poly}(n,m,\tau,L)$ |
| Coordinate projection | $\operatorname{poly}(n,m,\tau,L)$ |
| Switch family with $g(r)=0$ for all $r>K$ | $2^{O(K)}\operatorname{poly}_g(n,m,\tau,L)$ |
Minimum, product, and switch families with an eventual minimum tail are NP-hard under either flag. The constructed diagonal family has the general exponential upper bound and, assuming $\mathrm P\ne\mathrm{NP}$, belongs to neither of the proposed classes under either flag.
The source paper’s closed-form online updates do not change these conclusions. It explicitly uses subset dimension $2^n$, and its stated online running time remains exponential in $n$; its batch comparisons use linear programming. [Herin, Perny, and Sokolovska, *Online Learning of Capacity-Based Preference Models*](https://www.ijcai.org/proceedings/2024/0787.pdf).
The unconditional truth of the universal dichotomy remains unresolved, precisely because it is equivalent to $\mathrm P=\mathrm{NP}$. Membership in $\mathrm{NP}$ for the unrestricted diagonal family has also not been established here.
⟨structured verdict parsed — rendered above⟩
The substantive argument is sound. It establishes the stated polynomial cases, the stated hardness cases under both flag settings, and the conditional obstruction to a universal dichotomy. I found no false mathematical step or blocking gap.
There is one minor formalization issue in the computational construction: the enumeration and search-initialization conventions should be specified sufficiently to justify the uniform polynomial bound for evaluating the gate.
The output does not establish an unconditional classification of every permitted family. It explicitly acknowledges this limitation and proves that the proposed universal dichotomy is equivalent to $\mathrm P=\mathrm{NP}$. Leaving that equality unresolved is not a defect in the claimed conditional theorem.
Verified.
The LP correctly represents the original decision problem.
Because $\mu_t$ and $\lambda$ are positive, the final budget inequality cannot be satisfied by choosing epigraph variables below the actual losses or absolute values. Conversely, assigning those exact values extends every original feasible vector to an LP solution. Thus feasibility is equivalent in both directions.
The counts are correct:
$$
O(2^n+\tau)
$$
variables and
$$
O(n^2 2^n+\tau)
$$
constraints, with
$$
\sum_{S\subseteq N}2^{|S|}=3^n
$$
coefficient occurrences in the subset-sum equations.
The invoked LP theorem is applicable: feasibility of a finite rational linear system is decidable in polynomial time in its explicit binary encoding length. Uniform exact polynomial-time evaluation of the aggregators bounds their rational output lengths as well as evaluation time. Consequently, the claimed bound
$$
2^{O(n)}\operatorname{poly}_{\phi}(n,m,\tau,L)
$$
follows.
The use of real decision variables presents no additional issue: rational LP feasibility algorithms decide feasibility over the reals.
Verified under both flags.
The identity
$$
F_{\boldsymbol m}(x)=\sum_i a_i x_i
$$
follows directly from finite summation.
The permutation argument correctly establishes nonnegativity despite signed Möbius coefficients. For each fixed $S\ni i$, the relevant event is exactly that $i$ appears last among the elements of $S$, with probability $1/|S|$. The expected capacity marginal therefore equals $a_i$, and monotonicity makes every such marginal nonnegative.
Normalization gives
$$
\sum_i a_i=1.
$$
The replacement by singleton coefficients preserves all scores, defines an additive admissible capacity under either flag, and has regularizer norm $1$. The inequality
$$
1\leq\|\boldsymbol m\|_1
$$
is justified by the original normalization.
Both directions needed for equality of the optimization problems are present: every original solution admits a replacement with no larger objective, and every simplex weight vector defines an admissible original solution.
The resulting LP has polynomial encoding length. The polynomial-time classification is established.
Verified.
The switch family satisfies the task’s stated assumptions:
For an eventual projection tail, the identity
$$
a_i=v(\{1,\ldots,i\})-v(\{1,\ldots,i-1\})
$$
correctly groups all coefficients whose maximum label is $i$. Monotonicity therefore gives $a_i\geq0$.
The displayed replacement capacity preserves normalization and scores. Restriction to $H$ preserves monotonicity and supermodularity, and the additive extension preserves both properties. The regularizer comparison is a valid application of the triangle inequality within each coefficient group.
The converse extension is also admissible, so the reduced LP is equivalent to the original problem. The bound
$$
2^{O(K)}\operatorname{poly}_g(n,m,\tau,L)
$$
is valid for fixed $K$. Taking the gate identically zero establishes the coordinate-projection case.
The possibility $n\leq K$ is covered by the definition of $H$.
Verified with its stated hypotheses.
Normalization implies positive coefficient mass $1+\eta$ and negative coefficient mass $\eta$, hence
$$
\|\boldsymbol m\|_1=1+2\eta.
$$
The replacement is nonnegative, normalized, and satisfies
$$
\|\boldsymbol p-\boldsymbol m\|_1=2\eta.
$$
The equality accounts separately for negative coefficients and the reduction of positive coefficients.
The range assumption supplies $|b_t(S)|\leq1$. Both specified losses are indeed $1$-Lipschitz, and the report masses sum to $1$. Therefore the loss increase is at most $2\eta$, while the regularizer decreases by $2\lambda\eta$. The resulting objective comparison is correct for $\lambda\geq1$.
The case analysis establishing supermodularity of unanimity capacities is correct. Their nonnegative combination is consequently admissible under either flag.
The lemma is appropriately restricted. The output does not improperly apply it to arbitrary unbounded aggregators or arbitrary $\lambda$.
Verified under both flags.
The reduction respects the input restrictions.
The isolated-vertex padding gives
$$
\alpha(G)=\alpha(G_{\mathrm{original}})+h,
$$
and every maximum independent set contains the isolated vertex $n>K$. Thus at least one maximizing column uses the minimum branch.
The menu alternatives are distinct, and every report compares distinct alternatives. The unmerged report mass is $W/D$; the added opposite reports contribute $(D-W)/D$. Since $D>W$, all masses are positive dyadic rationals. Merging repeated types preserves the represented society and gives the claimed support-size upper bound.
For minimum columns, the edge calculation is correct:
$$
a_i-1+a_j-a_i a_j=-(1-a_i)(1-a_j).
$$
Accordingly,
$$
H(S)=|S|-C e_G(S).
$$
Independent columns have value $|S|$, while every nonindependent column has value at most $-1$ because $C=n+1$.
For projection columns, the vertex contribution is $1$, and each displayed edge contribution vanishes. Therefore those columns also satisfy the claimed upper bound.
Together these facts establish
$$
\max_{\varnothing\ne S\subseteq N}H(S)=\alpha(G).
$$
The signed replacement lemma applies because all relevant aggregator values lie in $[0,1]$ and $\lambda=1$. For nonnegative normalized coefficients, every report difference lies in $[-1,1]$, so with $\delta=2$ the strict loss is exactly $2-d_t$. Hence
$$
J(\boldsymbol p)
=
3-\frac1D\sum_{S\ne\varnothing}p(S)H(S)
$$
is correct. A maximizing unanimity capacity is admissible under either flag.
The threshold equivalence follows exactly:
$$
\min J\leq q
\quad\Longleftrightarrow\quad
\alpha(G_{\mathrm{original}})\geq k.
$$
The reduction is polynomial in size. The bounds on $m$, $\tau$, $D$, and the total explicit encoding length are consistent.
The product extension is valid: product and minimum agree on the binary menu, and product satisfies the replacement lemma’s range hypothesis. No additional hardness argument is being silently assumed.
Sound in substance, with one minor implementation clarification.
The four phase types cover both flag settings, every polynomial-time decider, and every polynomial-time candidate reduction from SAT.
A disagreement on one string defeats the corresponding decider or reduction. Target membership is decidable by Section 1, and SAT is decidable by exhaustive search. Membership in $\mathrm{NP}$ for the target languages is not needed.
The construction assigns each gate bit before advancing the search. A target computation reads assigned bits and waits for any unassigned bit it needs. Every finite target instance requires only finitely many gate bits, so its computation eventually resumes and terminates.
Consequently, the construction avoids circular oracle evaluation. Completed witnesses depend only on permanent gate values and remain valid thereafter.
Evaluating $g(r)$ requires simulation only through tick
$$
\lfloor\log_2 r\rfloor.
$$
The intended argument is valid: only that many background transitions occur, so a standard bounded universal simulation has polynomial overhead.
Minor issue: the output initially permits an arbitrary effective enumeration, while its resource argument implicitly assumes an efficiently represented enumeration and that enumeration, initialization, and restarting work are charged to the simulated computation. Those conventions should be made explicit. An arbitrary effective enumeration alone does not justify the asserted bound on configuration size or initialization cost.
Minimum clarification: specify the enumeration convention and confirm that search setup and machine-description generation occur within the background transition accounting. This is an implementation clarification; it does not require a new mathematical argument.
Both contradiction arguments are valid under $\mathrm P\ne\mathrm{NP}$.
Sequential exhaustive search examines every finite candidate during a permanent phase because each candidate’s computation eventually terminates.
Thus every requirement is satisfied. The resulting languages are outside $\mathrm P$ and are not $\mathrm{NP}$-hard under polynomial-time many-one reductions.
The cited [Ladner notes](https://web.cs.ucdavis.edu/~rogaway/classes/220/winter06/ladner-theorem.pdf) support the description of the technique. The output supplies its own construction rather than incorrectly invoking the classical theorem for languages of unproved $\mathrm{NP}$ membership.
Verified, subject to the minor convention above.
The constructed family establishes the forward implication by contraposition.
For the reverse implication, the fixed one-coordinate instances are correct. Their unique normalized coefficient gives objective $1$, making $q=1$ a yes-instance and $q=0$ a no-instance under either flag.
If $\mathrm P=\mathrm{NP}$, deciding any source language in $\mathrm{NP}$ and outputting the appropriate fixed instance is a polynomial-time many-one reduction. This establishes hardness without assuming target membership in $\mathrm{NP}$.
The equivalence is therefore justified. The absence of an unconditional resolution of $\mathrm P=\mathrm{NP}$ does not undermine it.
The algorithmic bounds follow from the verified LP constructions. The hardness results make no unsupported completeness or membership claims.
The source-paper summary is accurate: it states an online complexity of $O(Td)$ with $d=2^n$, and describes batch comparisons using linear programming. These claims do not supply polynomial-time exact optimization in $n$. See [Herin, Perny, and Sokolovska](https://www.ijcai.org/proceedings/2024/0787.pdf).
The output’s final self-description as “partial” reflects unresolved unconditional classification. Its principal conditional obstruction and equivalence are nevertheless established in substance.
For the requested status field, the overall result is other: it establishes a universal-dichotomy obstruction together with particular polynomial and hardness cases. It does not establish dependence on input encoding, so split would be inappropriate.
⟨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.