Answer: \(\mathrm{NP}\text{-complete}\)
Theorem 3 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateThe consistency modification problem is NP- complete, both for weak consistency and for consistency.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given alternatives \(A\), finite role types \(T\), rational masses \(\mu_t\) summing to \(1\), and a type-level delegation map \(\delta(t,\{a,b\})\), delete external rules \(D\) at cost \(\sum_{(t,\{a,b\})\in D}\mu_t\), and decide whether the remaining role graph admits complete transitive rankings \(R_t\) respecting every internal comparison and every surviving equality \(R_t|_{\{a,b\}}=R_{\delta(t,\{a,b\})}|_{\{a,b\}}\), within budget \(B\).
A society is given by its support: a list \(T\) of \(\tau\geq 1\) role types with positive binary rational masses \(\mu_t\), summing to \(1\); \(\tau\) is the support size, not the number of possible types.
Let \(A\) contain \(m\geq 2\) alternatives. Each type specifies every unordered pair of distinct alternatives either internally, with a strict comparison, or externally, with a delegate \(\delta(t,\{a,b\})\in T\setminus\{t\}\). Each type's internal comparisons form a strict partial order.
Let \(E\) be the set of external rules. A deletion chooses \(D\subseteq E\), costing \(\sum_{(t,\{a,b\})\in D}\mu_t\); each rule is deleted for its entire source type. Deleted pairs become unconstrained, and internal comparisons cannot be changed.
Given a nonnegative binary rational budget \(B\), feasibility means that some deletion of cost at most \(B\) admits one strict linear order \(R_t\) per type, extending its internal comparisons and satisfying \(R_t|_{\{a,b\}}=R_{\delta(t,\{a,b\})}|_{\{a,b\}}\) for every surviving rule. Here restriction denotes the comparison on that pair. Delegation cycles are allowed and must satisfy these same equalities.
Let \(L\) be the total binary input length; state running times in \(m,\tau,L\).
Is this mass-weighted consistency modification decision problem in \(\mathrm{P}\), or is it \(\mathrm{NP}\)-hard?
For finite voters with unit deletion costs, consistency modification is \(\mathrm{NP}\)-complete for both consistency and weak consistency; consistency testing itself is also \(\mathrm{NP}\)-complete. [Source](https://comsoc-community.org/assets/proceedings/comsoc-2018/BrillTalmonCOMSOC2018.pdf)
No result settling exactly the support-based, mass-weighted problem above was identified in the searches.
The problem is \(\mathrm{NP}\)-complete. Hardness holds even when all masses are equal, only one type has external rules, and there are no delegation cycles.
A certificate consists of one permutation \(R_t\) of the alternatives for each type \(t\).
First check that every \(R_t\) extends its type’s internal comparisons. For such a profile, define
\[
D_R=\bigl\{(t,\{a,b\})\in E:
R_t|_{\{a,b\}}\ne R_{\delta(t,\{a,b\})}|_{\{a,b\}}\bigr\}.
\]
Every feasible deletion admitting this profile must delete all rules in \(D_R\), because each surviving rule requires equality of the corresponding comparisons. Conversely, deleting exactly \(D_R\) makes every surviving rule satisfied. Thus the certificate is accepted precisely when
\[
\sum_{(t,\{a,b\})\in D_R}\mu_t\le B.
\]
There are at most \(\tau\binom m2\) rules. The certificate has length \(\mathcal O(\tau m\log m)\), and its comparisons can be checked using position tables. Exact rational arithmetic also takes polynomial time: a common denominator obtained by multiplying the input denominators has bit length at most \(L\); the deletion counts introduce only \(\mathcal O(\log m)\) additional bits. A conservative bound for the entire verification is \(\mathcal O((L+\tau m^2)^3)\) bit operations.
Therefore the problem belongs to \(\mathrm{NP}\).
We reduce from Feedback Arc Set in Tournaments. Its input is a tournament \(H=(V,F)\) and a nonnegative integer \(k\); the question is whether some \(F'\subseteq F\), with \(|F'|\le k\), makes \((V,F\setminus F')\) acyclic.
This decision problem is \(\mathrm{NP}\)-complete, by the deterministic hardness result of Charbit, Thomassé, and Yeo. A tournament has exactly one directed arc between every two distinct vertices. [Source](https://perso.ens-lyon.fr/stephan.thomasse/liste/feedback.pdf)
We may restrict to \(|V|\ge2\) and \(0\le k\le |F|\): the excluded instances are immediately decidable.
Set \(A=V\), \(m=|V|\), and \(N=|F|=\binom m2\). Create the following \(\tau=N+1\) types:
For every arc \(e=(x,y)\), let the central type delegate the pair \(\{x,y\}\) to \(t_e\).
Give every type mass \(\mu_t=1/\tau\), and set \(B=k/\tau\).
Every pair is specified exactly once for every type. Each internal relation is a strict partial order: it is empty for \(s\) and a strict linear order for each \(t_e\). Every delegate differs from its source, and every delegation leads directly to a type with only internal comparisons.
The types are distinct even if “support” requires distinct role descriptions: different arc types have different first two alternatives in their internal orders, while \(s\) has external rules. All masses are positive binary-encoded rationals and sum to \(1\).
The construction explicitly writes \(\tau\binom m2\) pair specifications. Its output length and construction time are \(\mathcal O(m^4\log m)\), using \(\tau=1+\binom m2\) and \(k\le N\).
Suppose \(F'\subseteq F\), \(|F'|\le k\), and \((V,F\setminus F')\) is acyclic.
Delete precisely the central type’s rules corresponding to arcs in \(F'\). Their cost is
\[
\frac{|F'|}{\tau}\le\frac{k}{\tau}=B.
\]
A finite acyclic directed graph has a topological ordering. For completeness, it has a vertex of indegree zero: otherwise, repeatedly following incoming arcs would eventually repeat a vertex and produce a directed cycle. Removing such a vertex and applying induction produces an ordering in which every arc points forward.
Use this ordering as \(R_s\), with earlier alternatives ranked above later ones. Set \(R_{t_e}=Q_e\) for every arc type.
For each surviving rule associated with \(e=(x,y)\), the topological ordering ranks \(x\) above \(y\). The delegate’s order \(Q_e\) also ranks \(x\) above \(y\). Hence every surviving rule is satisfied, and every internal comparison is extended.
Conversely, suppose a deletion \(D\) of cost at most \(B\) admits the required linear orders.
Only the central type has external rules. Thus \(D\) corresponds to an arc set \(F'\subseteq F\), and
\[
\frac{|F'|}{\tau}=\operatorname{cost}(D)\le\frac{k}{\tau},
\]
so \(|F'|\le k\).
For every surviving arc \(e=(x,y)\), the delegate’s fully internal order forces \(R_{t_e}=Q_e\). The surviving delegation therefore forces \(x\) above \(y\) in \(R_s\).
Consequently, every arc of \(F\setminus F'\) points forward in the single linear order \(R_s\). A directed cycle would force an alternative to precede itself, contradicting transitivity and irreflexivity. Hence \((V,F\setminus F')\) is acyclic.
This proves the required equivalence.
The polynomial reduction establishes \(\mathrm{NP}\)-hardness, and the certificate argument establishes membership in \(\mathrm{NP}\). Normalizing the masses simply scales every available deletion cost and the budget by the same factor.
If “binary rational” specifically means a dyadic rational, hardness still follows: choose a power of two \(q\ge\tau\), give every type mass \(1/q\), and add the remaining mass \(1-\tau/q\) to one fully internal type. Set \(B=k/q\). Only the central type’s mass affects deletion costs, so the same proof applies.
⟨structured verdict parsed — rendered above⟩
The prover resolves the assigned problem. The reduction establishes \(\mathrm{NP}\)-hardness for the specified support-based, mass-weighted model, and the certificate argument establishes membership in \(\mathrm{NP}\). I found no major or minor issues requiring repair.
The proposed certificate specifies one permutation for each supported type. Its length, \(\mathcal O(\tau m\log m)\), is polynomial in the explicit input size.
The verifier must check that these are permutations and that they extend all internal comparisons. Position tables then allow each external rule’s equality constraint to be checked.
The definition of \(D_R\) correctly identifies exactly the external rules violated by the certified profile:
Consequently, testing the cost of \(D_R\) is both necessary and sufficient for this certificate. No separate deletion certificate is needed. This reasoning also covers delegation cycles: the verifier checks each surviving equality directly.
The rational-arithmetic bound is sound. The product of the input denominators has bit length at most \(L\). Each type contributes its mass multiplied by a deletion count bounded by \(\binom m2\). Because the masses sum to \(1\), the total deletion cost is at most \(\binom m2\), so its numerator over that common denominator requires only \(\mathcal O(\log m)\) additional bits. Comparison with the binary rational budget remains polynomial. The stated conservative verification bound, \(\mathcal O((L+\tau m^2)^3)\), is adequate.
The source decision problem is stated precisely: delete at most \(k\) arcs from a tournament so that the remaining directed graph is acyclic.
The cited deterministic tournament feedback-arc-set hardness result is applicable. The paper establishes polynomial hardness for the minimum feedback arc set in tournaments; its threshold decision version is \(\mathrm{NP}\)-complete. [Charbit, Thomassé, and Yeo](https://perso.ens-lyon.fr/stephan.thomasse/liste/feedback.pdf)
Restricting to \(m\ge2\) and \(0\le k\le |F|\) removes only immediately decidable instances and does not invalidate the hardness source.
Every requirement of the target model is satisfied:
The distinctness argument is correct. An arc type’s full order determines its first two alternatives, so two different arcs cannot produce the same order. The central type has a different role description because its pair specifications are external.
There are \(\tau\binom m2=\mathcal O(m^4)\) pair specifications. Their identifiers require \(\mathcal O(\log m)\) bits, making the claimed construction time and output length \(\mathcal O(m^4\log m)\) valid.
Given a feedback arc set \(F'\), deleting the corresponding central rules costs exactly \(|F'|/\tau\), which is within budget.
The topological-order argument is valid for the remaining finite acyclic graph, including when it has no arcs. Every surviving arc points forward in \(R_s\), while its delegate’s prescribed order places the same source alternative above the same target alternative. Thus every surviving equality and every internal comparison is satisfied.
Only the central type has deletable rules. Therefore any feasible deletion corresponds exactly to an arc subset \(F'\), with cost \(|F'|/\tau\). The budget inequality implies \(|F'|\le k\).
Every delegate’s complete internal order forces its certified order to equal \(Q_e\). Each surviving rule therefore forces its corresponding arc to point forward in the central linear order. A directed cycle cannot have all its arcs pointing forward in a strict linear order. The remaining graph is consequently acyclic.
This establishes both directions of the reduction without assuming anything about comparisons on deleted pairs.
The optional dyadic construction is also valid: all resulting masses remain positive, sum to \(1\), and have polynomial encoding length. The central mass remains \(1/q\), so the same cost equivalence applies.
That variant generally has unequal masses. The equal-mass strengthening in the main result is valid under the task’s ordinary meaning of binary-encoded rational numbers.
No additional clarification is needed to verify the main conclusion.
⟨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.