Answer: NP-hard, even with \(m=\tau=1\), sole mass \(1\), and \(R_x=R_g=\varnothing\).
Theorem 3 — class: other
PDF text-layer excerpt — equations and symbol order may be approximateGiven a norm net ⟨N, R⟩and a value system ⟨V, ⪰⟩, the solution to the most value-aligned norm system selection problem (Ω∗) and the solution to the problem of finding the norm system with maximum value alignment (Ωmax ) are the same, namely Ω∗= Ωmax. In case the solution is not unique, then Ω∗∼∗ ΩΩmax.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite norm net \(\langle N,R\rangle\), value set \(V\), support map, and rational-mass distribution \(\mu\) over \(\tau\) complete weak rankings \(\succeq_t\) of \(V\), define \(M_\mu(v,w)=\sum_{t:v\succeq_t w}\mu_t\) and \(v\succeq_\mu w\) iff \(M_\mu(v,w)\ge \tfrac12\). For inputs where \(\succeq_\mu\) is transitive, find a sound \(\Omega\subseteq N\) maximizing the norm-system ranking induced from \(\succeq_\mu\) by preference induction, lex-cel grounding, and anti-lex-cel lifting.
Let \(N\) be a nonempty finite set of candidate norms, \(V\) a nonempty finite value set, \(q=|N|\), and \(m=|V|\). The explicitly listed norm relations are symmetric irreflexive exclusivity \(R_x\), symmetric irreflexive substitutability \(R_s\), and acyclic directed generalisation \(R_g\), with \((n,n')\in R_g\) meaning that \(n\) directly generalises \(n'\).
Write \(A(n)\) for the ancestors of \(n\) under \(R_g\), and \(D(n)=\{n':(n,n')\in R_g\}\). A system \(\Omega\subseteq N\) is sound if it contains no exclusive or substitutable pair, no norm together with an ancestor, and never contains all of \(D(n)\) when \(|D(n)|>1\).
The explicit promotion map \(\sigma_v:N\to 2^V\) has nonempty images, and every value is promoted. Require \(\sigma_v(n)\cap\sigma_v(n')=\varnothing\) for exclusive norms and \(\sigma_v(n')\subseteq\sigma_v(n)\) whenever \((n,n')\in R_g\). Put \(S_v=\{n:v\in\sigma_v(n)\}\).
A society is given by its support: the list of the \(\tau\) types with positive mass, each mass a binary rational. Each type is a complete weak ranking \(\succeq_t\) of \(V\); \(\tau\) is the support size, not the number of possible rankings. Require \(\sum_t\mu_t=1\), and define \(M_\mu(v,w)=\sum_{t:v\succeq_t w}\mu_t\) and \(v\succeq_\mu w\iff M_\mu(v,w)\ge\tfrac12\).
Promise that \(\succeq_\mu\) is transitive and that \(S_v=S_w\) implies \(v\sim_\mu w\). Preference induction ranks the distinct sets \(S_v\) by \(S_v\succeq S_w\iff v\succeq_\mu w\); all other subsets of \(N\) form one strictly last indifference class.
For these subset classes \(\Sigma_1,\ldots,\Sigma_k\), ordered best first, lex-cel ranks norms by lexicographically comparing \(c(n)=(|\{S\in\Sigma_i:n\in S\}|)_{i=1}^k\). Let \(\Xi_1,\ldots,\Xi_r\) be the resulting norm indifference classes, best first. Anti-lex-cel ranks systems by lexicographically comparing \(\eta(\Omega)=(|\Omega\cap\Xi_i|)_{i=1}^r\), with equal vectors tied.
Find a sound \(\Omega\subseteq N\) maximizing this ranking; any tied optimum is acceptable. Norm selection remains integral. State running times in \(m,\tau,q,L\), where \(L\) is the total binary input length.
Is this rational-mass norm-system optimization problem solvable in polynomial time, or is it NP-hard?
For a supplied value ranking, qualitative optima coincide with maximum additive value-alignment optima ([2020 equivalence result](https://www.ifaamas.org/Proceedings/aamas2020/pdfs/p1233.pdf)).
A later generalization provides an equivalent binary integer program ([2021 result](https://link.springer.com/article/10.1007/s10458-021-09519-5)); no result for this exact rational-mass problem was located.
The optimization problem is NP-hard, even when \(m=\tau=1\), all masses are integral, and \(R_x=R_g=\varnothing\). In this restricted case, it is exactly maximum independent set.
The rational society and the induced rankings can be processed in polynomial time. The hardness remains in selecting an integral sound system.
Write each positive mass as \(\mu_t=a_t/b_t\), where \(a_t,b_t\) are positive integers represented in binary. Set
\[ Q=\prod_{t=1}^{\tau}b_t,\qquad p_t=a_t(Q/b_t). \]
These integers have \(O(L)\) bits. Every majority comparison can be computed exactly using
\[ v\succeq_\mu w \iff 2\sum_{t:v\succeq_t w}p_t\ge Q. \]
Thus all comparisons require \(O(\tau m^2L^2)\) bit operations using elementary integer arithmetic.
For each type, completeness of its weak ranking gives
\[ \mathbf 1[v\succeq_t w]+\mathbf 1[w\succeq_t v]\ge 1. \]
Consequently, \(M_\mu(v,w)+M_\mu(w,v)\ge 1\), so the majority relation is complete. It is reflexive because \(M_\mu(v,v)=1\), and transitive by promise. Hence it is a total preorder.
The promise concerning equal promotion sets makes the induced ranking well-defined. Indeed, in any transitive relation, if \(v\sim_\mu v'\), then \(v\succeq_\mu w\) holds exactly when \(v'\succeq_\mu w\), by applying transitivity in both directions. The same argument applies to the second argument of the comparison.
There are at most \(m\) distinct promotion sets. Let their indifference classes, ordered best first, be \(C_1,\ldots,C_h\), where \(h\le m\). These classes contain distinct sets, so repeated values with the same promotion set are counted only once.
For a norm \(n\), define
\[ a_i(n)=|\{S\in C_i:n\in S\}|. \]
Every value is promoted, so every distinguished set \(S_v\) is nonempty. Therefore the class containing all other subsets is nonempty: it contains \(\varnothing\).
Exactly \(2^{q-1}\) subsets of \(N\) contain any fixed norm. It follows that the full lex-cel vector is
\[ c(n)=\left(a_1(n),\ldots,a_h(n), 2^{q-1}-\sum_{i=1}^{h}a_i(n)\right). \]
The last coordinate cannot distinguish norms whose preceding coordinates agree. Thus comparing the shorter vectors \((a_1(n),\ldots,a_h(n))\) gives exactly the required norm ranking. No enumeration of \(2^N\) is necessary.
Using direct pairwise comparisons to deduplicate promotion sets and rank norms, and a transitive-closure computation for \(R_g\), a conservative polynomial preprocessing bound is
\[ P(m,\tau,q,L) = O\!\left( (\tau m^2+m^3+m^2q+q^2m+q^3)L^2 \right). \]
This bound also allows checking the stated promises: majority transitivity takes \(O(m^3)\) comparisons, and the remaining structural and promotion conditions can be checked within the other terms.
We use the standard NP-complete problem Independent Set: given a nonempty simple undirected graph \(G=(U,E)\) and an integer \(K\), determine whether some subset of at least \(K\) vertices contains no edge.
Construct the norm instance as follows:
The construction has polynomial size and satisfies every hypothesis:
Since \(R_x\) and \(R_g\) are empty, soundness requires precisely that no two selected norms form a pair in \(R_s\). Therefore
\[ \Omega\text{ is sound} \iff \{u:n_u\in\Omega\}\text{ is independent in }G. \]
It remains to verify the objective. The sole distinguished promotion set is \(S_v=N\). Every norm therefore has the same vector
\[ c(n)=(1,2^{q-1}-1). \]
There is exactly one norm indifference class, \(\Xi_1=N\), and consequently
\[ \eta(\Omega)=(|\Omega|). \]
Thus the required optimum is exactly a maximum independent set. Given any tied optimum, its cardinality decides whether \(G\) has an independent set of size at least \(K\).
The reduction has \(m=\tau=1\), uses only the mass \(1\), and has output length polynomial in the graph’s explicit input length. Therefore an algorithm polynomial in \(m,\tau,q,L\) would solve Independent Set in polynomial time. This proves NP-hardness.
This hardness also holds with \(R_s=R_g=\varnothing\). To see this, instead use \(R_x\) for the graph edges, give each norm its own distinct value, and let the sole society type tie all values. Exclusive norms then promote disjoint values. The distinguished sets are tied singletons, every norm again has vector \((1,2^{q-1}-1)\), and the same independent-set argument applies.
For completeness, the objective has a polynomial-size additive encoding. Let \(\Xi_1,\ldots,\Xi_r\) be the computed norm classes and set \(B=q+1\). Assign each norm in \(\Xi_i\) weight \(B^{r-i}\). Define
\[ F(\Omega)=\sum_{i=1}^{r}|\Omega\cap\Xi_i|B^{r-i}. \]
This objective induces exactly the specified lexicographic ranking. If two vectors first differ at coordinate \(i\), a positive difference there contributes at least \(B^{r-i}\). The absolute contribution from all later coordinates is at most
\[ q\sum_{j=i+1}^{r}B^{r-j} = B^{r-i}-1. \]
Hence later coordinates cannot reverse the first strict comparison. Equal vectors give equal objectives. Since \(r\le q\), the weights and objective have \(O(q\log(q+1))\) bits.
Introduce binary variables \(x_n\), indicating membership in \(\Omega\). Soundness is exactly expressed by
\[ x_n+x_{n'}\le 1 \quad\text{for every exclusive or substitutable pair}, \]
\[ x_n+x_a\le 1 \quad\text{for every }a\in A(n), \]
\[ \sum_{n'\in D(n)}x_{n'}\le |D(n)|-1 \quad\text{whenever }|D(n)|>1, \qquad x_n\in\{0,1\}. \]
Maximizing the corresponding weighted sum is therefore an exact binary integer formulation.
The natural threshold decision problem—whether some sound system has \(F(\Omega)\ge K\)—is in NP: a proposed system can be checked for soundness and its objective computed in polynomial time. Together with the reduction, this decision problem is NP-complete.
An unconditional exact algorithm computes the ranking, enumerates all \(2^q\) systems, and retains a sound system with the best vector. Its conservative bit-operation bound is
\[ O\!\left( (\tau m^2+m^3+m^2q+q^2m+q^3+2^q q^2)L^2 \right), \]
with polynomial space.
The [2020 encoding](https://www.ifaamas.org/Proceedings/aamas2020/pdfs/p1233.pdf) explicitly uses binary selection variables, and the [2021 generalization](https://link.springer.com/article/10.1007/s10458-021-09519-5) gives a binary integer program. Equivalence to an additive objective does not remove the integrality requirement.
For example, take the one-value construction above on a triangle. Its integral optimum has cardinality \(1\). If the binary restrictions are relaxed to \(0\le x_n\le 1\), assigning \(1/2\) to each of the three norms satisfies every pair constraint and gives objective \(3/2\). Thus the continuous relaxation does not, in general, recover a sound integral optimum.
The classification is therefore complete: the specified rational-mass optimization problem is NP-hard, including the constant-\(m\), constant-\(\tau\) restriction proved above.
⟨structured verdict parsed — rendered above⟩
The prover resolves the assigned problem correctly: the integral norm-system optimization problem is NP-hard, including the restriction \(m=\tau=1\). The ranking computation is polynomial, the reduction preserves every promise, and the additional integer formulation and exhaustive-search bound are valid. No major or minor mathematical issues were found.
The common denominator \(Q=\prod_t b_t\) has bit length bounded by the sum of the denominator bit lengths, hence \(O(L)\). Each \(p_t=a_t(Q/b_t)\) likewise has \(O(L)\) bits. Since the masses are positive and sum to \(1\), sums used in comparisons are bounded by \(Q\).
Multiplying the majority inequality by the positive number \(2Q\) gives exactly the stated integer comparison. The bound \(O(\tau m^2L^2)\) accommodates constructing these integers and evaluating all ordered value comparisons using elementary arithmetic.
Completeness follows from the indicator inequality and normalization of the masses. Reflexivity follows from \(M_\mu(v,v)=1\). Transitivity is explicitly promised, so the conclusion that the majority relation is a total preorder is justified.
The equal-promotion-set promise supplies mutual majority preference whenever two values represent the same set. Transitivity then makes those values interchangeable in either argument of a comparison. Thus ranking distinct promotion sets does not depend on the chosen representatives.
Deduplicating promotion sets before counting their occurrences correctly respects the task’s definition: the objects being ranked are subsets, rather than values counted with multiplicity.
Every \(S_v\) is nonempty because every value is promoted. Therefore \(\varnothing\) belongs to the residual, strictly last subset class, so that class exists even in the smallest permitted instances.
The count \(2^{q-1}\) of subsets containing a fixed norm is correct for every \(q\ge1\). Subtracting the distinguished subsets containing that norm gives precisely the displayed last coordinate of \(c(n)\).
If all preceding coordinates agree for two norms, their subtracted totals agree as well. Consequently, the last coordinate cannot break a tie, and comparing the shorter vectors produces exactly the required ranking.
The stated preprocessing bound is conservative but valid. It covers exact majority comparisons, transitivity checks, promotion-set construction and deduplication, norm comparisons, graph closure, and checking the structural promises.
The invoked Independent Set decision problem is stated precisely, with a simple undirected graph and a cardinality threshold. Restricting to nonempty graphs does not remove its standard NP-completeness.
Each constructed norm instance meets the task’s requirements:
With exclusivity and generalisation absent, the only soundness restrictions are the graph-edge substitutability restrictions. Thus sound systems correspond exactly to independent sets.
The objective calculation is also correct: \(S_v=N\), every norm has vector \((1,2^{q-1}-1)\), and all norms lie in one indifference class. Hence \(\eta(\Omega)=(|\Omega|)\). Every tied optimum therefore has maximum independent-set cardinality.
The construction has polynomial explicit size. Returning any optimal system suffices to decide the original threshold question. This establishes the claimed optimization hardness without relying on either cited equivalence result.
Assigning one distinct value to each norm makes promotion images disjoint for exclusive pairs. A single type tying all values produces tied singleton promotion sets.
Each norm belongs to exactly one distinguished singleton, giving the stated common vector. Soundness again matches independence, and the objective again maximizes cardinality. This additional claim is valid, although its value count grows with \(q\); the prover does not claim otherwise.
With \(B=q+1\), every system count lies between \(0\) and \(q=B-1\). The stated geometric-series calculation is correct:
\(q\sum_{j=i+1}^{r}B^{r-j}=B^{r-i}-1\).
Therefore later coordinates cannot cancel a positive difference at the first differing coordinate. The additive objective preserves strict comparisons and ties.
Since \(r\le q\), the weights and objective have the claimed polynomial bit length.
Each binary constraint matches its corresponding soundness requirement exactly. In particular, the direct-successor constraint is imposed whenever \(|D(n)|>1\), regardless of whether \(n\) itself is selected, as the task requires.
A proposed system has a polynomial-size certificate. The established preprocessing procedure allows checking the promises, computing its ranking objective, and verifying soundness in polynomial time. The threshold decision problem is therefore in NP.
In the primary reduction there is only one norm class, so \(F(\Omega)=|\Omega|\). This verifies that the same reduction also establishes NP-hardness of the threshold formulation, yielding its claimed NP-completeness.
Enumerating all \(2^q\) subsets and checking each against precomputed relations and norm classes fits the stated conservative time bound. Retaining only the current and best systems, together with polynomial-size preprocessing data, gives polynomial space.
The bibliographic claims are accurate: the [2020 paper](https://www.ifaamas.org/Proceedings/aamas2020/pdfs/p1233.pdf) explicitly uses binary selection variables, and the [2021 paper](https://link.springer.com/article/10.1007/s10458-021-09519-5) provides a binary integer encoding.
For the triangle example, every integral independent set has size at most \(1\), while assigning \(1/2\) to all three variables satisfies every pair constraint and gives objective \(3/2\). This correctly demonstrates that the continuous relaxation need not return an integral optimum. The hardness conclusion concerns the task’s integral optimization problem; the prover does not establish hardness of its fractional relaxation.
No additional clarification or repair is needed.
⟨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.