Answer: NP-hard
Theorem 5 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateFinding an optimal subset of a given set of items (POS) with respect to a GAI prefer- ence specification is NP-hard even if the items are described in terms of a single attribute, all the set properties are binary-valued, each containing at most 1 logical connective (that is, we have a = 1 and k = 1).
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite support \(T\) of one-attribute profiles with rational supply masses \(\mu_t>0\) summing to \(1\), choose selected masses \(x_t\in[0,\mu_t]\). Replace each paper-style count property on \(\phi\) by a quota predicate \(\sum_{t\models\phi}x_t\bowtie q\), where \(q\) is rational and \(\bowtie\) includes equality and inequalities. Given a GAI utility over the resulting Boolean property values, compute a mass vector \(x\) that maximizes that utility.
A society is given by its support: a list \(T\) of \(\tau\) distinct types with positive binary-rational masses \(\mu_t\) summing to \(1\). Here \(\tau\) is the support size, not the number of possible types. Each type specifies the value of one categorical attribute \(A\) in an explicitly listed finite domain.
There are \(m\) Boolean properties. Each formula \(\phi_i\) consists of equality atoms \(A=a\) and at most one logical connective from \(\{\land,\lor,\neg\}\); no empty formula is allowed.
A selection is a vector of real masses \(0\le x_t\le\mu_t\), with no prescribed total selected mass; the zero vector is allowed. Define \(P_i(x)=\mathbf{1}[\sum_{t\models\phi_i}x_t\bowtie_i q_i]\), where \(q_i\) is a nonnegative binary rational and \(\bowtie_i\in\{=,\ne,<,\le,>,\ge\}\). Comparisons are exact.
The input GAI utility is \(U(x)=\sum_{j=1}^{r}u_j((P_i(x))_{i\in I_j})\), with explicitly listed scopes \(I_j\subseteq\{1,\ldots,m\}\) and complete tables of signed binary-rational values. Let \(L\) be the total input bit length. Any maximizing selection is acceptable.
Is computing an exact utility-maximizing mass vector solvable in time polynomial in \(m,\tau,r,L\), or is it NP-hard?
For finite item sets, exact subset optimization is NP-hard even with one categorical attribute, Boolean properties containing at most one connective, and additive unary utilities (Binshtok et al., 2009).
That discrete result does not establish the complexity of the normalized mass problem defined above.
Computing an exact utility-maximizing mass vector is NP-hard, even with additive unary utilities, thresholds all equal to zero, and only the comparison \(>\).
We prove this by a polynomial-time reduction from Vertex Cover. We use its standard NP-completeness: given a finite simple undirected graph \(G=(V,E)\) and an integer \(k\) with \(0\le k\le |V|\), deciding whether some set of at most \(k\) vertices meets every edge is NP-complete.
Let \(n=|V|\ge 1\), and let \(N\) be the smallest power of two satisfying \(N\ge n\).
Give the categorical attribute \(A\) one distinct value \(a_v\) for each vertex \(v\in V\). Include a corresponding type \(t_v\) of mass
\(\mu_{t_v}=1/N\).
If \(N>n\), also include a distinct value \(a_*\) and corresponding type \(t_*\) of mass
\(\mu_{t_*}=(N-n)/N\).
If \(N=n\), omit this extra type.
Thus all listed masses are positive dyadic rationals and sum to one. The support size is at most \(n+1\).
Introduce the following properties, all with threshold zero and comparison \(>\):
Every formula is nonempty and has at most one permitted connective.
There is one unary utility factor for each property. Its complete table is:
| Factor | Value at \(0\) | Value at \(1\) |
|---|---:|---:|
| Vertex \(v\) | \(0\) | \(-1\) |
| Edge \(e\) | \(-(n+1)\) | \(0\) |
Consequently, \(m=r=n+|E|\), and every scope is a singleton.
The categorical domain, formulas, masses, scopes, and tables all have polynomial encoding length in the graph input. In particular, \(N<2n\), the mass encodings require \(O(\log n)\) bits each, and the utility entries require \(O(\log n)\) bits.
For any feasible mass vector \(x\), define its active vertex set by
\(C(x)=\{v\in V:x_{t_v}>0\}\).
Because selected masses are nonnegative, for every edge \(e=\{u,v\}\) we have
\(x_{t_u}+x_{t_v}>0\) if and only if at least one of \(x_{t_u},x_{t_v}\) is positive. Therefore
\(P_e(x)=1\) if and only if \(e\cap C(x)\ne\varnothing\).
Let \(h(C)\) denote the number of edges having neither endpoint in \(C\). Substituting the utility tables gives the exact identity
\(U(x)=-|C(x)|-(n+1)h(C(x))\).
Conversely, every subset \(C\subseteq V\) is realizable: choose \(x_{t_v}=\mu_{t_v}\) for \(v\in C\), choose \(x_{t_v}=0\) otherwise, and choose \(x_{t_*}=0\) if the extra type exists. This is feasible and has active vertex set exactly \(C\).
Thus optimizing over the continuous mass vectors is exactly equivalent, for these instances, to optimizing this expression over all vertex subsets. In particular, a maximum exists and has a rational representative.
The set \(V\) covers every edge, so its representative has utility \(-n\).
If \(C(x)\) fails to cover some edge, then \(h(C(x))\ge 1\), and hence
\(U(x)\le -(n+1)<-n\).
Such a vector cannot maximize utility, because the representative of \(V\) has strictly greater utility.
Every maximizing vector therefore has a vertex cover as its active vertex set. For a vertex cover \(C\), the identity above simplifies to
\(U(x)=-|C|\).
It follows that every maximizing vector has a minimum vertex cover as its active vertex set. Writing \(\kappa(G)\) for the minimum vertex-cover size, we obtain
\(\max_x U(x)=-\kappa(G)\).
An algorithm computing any exact maximizing vector would solve Vertex Cover: construct the instance above, obtain its maximizing vector, extract the vertices whose masses are positive, and compare their number with \(k\). These are exact comparisons of the kind stipulated in the question.
Equivalently, the constructed instance satisfies
\(\max_x U(x)\ge -k\) if and only if \(G\) has a vertex cover of size at most \(k\).
This proves NP-hardness under a polynomial-time reduction. Therefore a polynomial-time algorithm in \(m,\tau,r,L\) would imply \(\mathrm{P}=\mathrm{NP}\).
⟨structured verdict parsed — rendered above⟩
The proof is correct and resolves the task: computing an exact maximizing mass vector is NP-hard under the stated restrictions. No major or minor mathematical issues were found.
The stated Vertex Cover decision problem is NP-complete for finite simple undirected graphs. Restricting to \(n\ge 1\) does not affect hardness: the excluded empty graph is a trivial instance. The restriction \(0\le k\le n\) likewise removes only trivially decidable cases.
The smallest power of two \(N\ge n\) satisfies \(n\le N<2n\), including \(n=1\). Each vertex type has positive mass \(1/N\). When present, the extra type has positive mass \((N-n)/N\). The total mass is exactly
\[
\frac{n}{N}+\frac{N-n}{N}=1.
\]
When \(N=n\), the vertex masses alone sum to one. All masses are dyadic rationals, all attribute values are distinct, and the support size is at most \(n+1\). The construction meets the task’s support and domain requirements.
A vertex formula has no connective; an edge formula has exactly one disjunction. Both are nonempty and use permitted equality atoms. Threshold zero and comparison \(>\) are allowed. Each unary factor has its complete two-entry table, with permitted signed rational values.
The counts \(m=r=n+|E|\) are correct. The explicitly listed domain, formulas, singleton scopes, masses, and tables have polynomial total encoding length. The stated bounds on mass and utility encodings are correct.
Feasibility supplies the nonnegativity needed for
\[
x_{t_u}+x_{t_v}>0
\quad\Longleftrightarrow\quad
x_{t_u}>0\ \lor\ x_{t_v}>0.
\]
Thus vertex properties identify the active set, and edge properties identify its covered edges. Summing the tables gives exactly
\[
U(x)=-|C(x)|-(n+1)h(C(x)).
\]
The extra type affects no property.
Conversely, the proposed representative of every subset satisfies all mass bounds and realizes precisely that subset. Therefore the continuous instance has exactly the utility values of the finite subset problem. This also justifies existence of a maximum despite the strict comparisons; a rational maximizing representative exists.
Selecting all vertices gives utility \(-n\). Any noncover has \(h(C)\ge1\), so its utility is at most \(-(n+1)\), strictly below \(-n\). Hence every maximizer activates a vertex cover.
On covers, utility equals minus cardinality. Since every cover is realizable, every maximizing vector activates a minimum cover, and
\[
\max_x U(x)=-\kappa(G).
\]
This remains valid for edgeless graphs: the empty active set attains utility zero and is a minimum cover.
The equivalence
\[
\max_x U(x)\ge-k
\quad\Longleftrightarrow\quad
\kappa(G)\le k
\]
establishes a polynomial reduction to the utility-threshold decision problem. For the requested optimization problem, any exact maximizing vector yields a minimum cover by inspecting its positive vertex coordinates. This uses the exact-comparison convention stated in the task.
Since all constructed parameters and the total input length are polynomially bounded in the graph input, the claimed implication to \(\mathrm{P}=\mathrm{NP}\) follows.
No repair or additional mathematical clarification is needed. The argument directly addresses normalized continuous masses and does not rely on transferring the discrete result.
⟨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.