Answer: The decision problem is in \(\mathrm{P}\), and \(M\) can be computed exactly in polynomial time.
Corollary 1 (Consistency) — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateLet conditional preference the- ory Γ be such that G(Γ) is acyclic. Then Γ is consistent if and only if Γ is locally consistent. This shows that, as long as Γ is chosen so that the as- sociated order G(Γ) on variables is acyclic, and the local consistency property is confirmed, then Γ is guaranteed to be consistent and the associated order on outcomes will be irreflexive (and hence acyclic). It gives an agent consider- able flexibility in making their preference statements, with- out risking inconsistency.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given Boolean variables \(V\), a finite support \(T\) of conditional preference theories \(\Gamma_t\) with rational masses \(\mu_t\) summing to \(1\), and acyclic \(G(\Gamma_t)\) for every type, compute \(M=\sum_{t:\,\Gamma_t\text{ is consistent}}\mu_t\), or decide whether \(M\ge q\) for a given rational threshold \(q\).
Let \(V\) contain \(m\) Boolean variables, with outcomes \(\{0,1\}^{V}\). A theory \(\Gamma\) is an explicitly listed finite set of statements \(u:x>x'[W]\), where \(u\) assigns \(U\subseteq V\), \(X\in V\setminus U\), \(x,x'\in\{0,1\}\) are distinct values of \(X\), and \(W\subseteq V\setminus(U\cup\{X\})\).
Such a statement requires every outcome satisfying \(u\) and \(X=x\) to precede every outcome satisfying \(u\) and \(X=x'\) that agrees with it outside \(W\cup\{X\}\). A theory is consistent if some strict total order on outcomes satisfies all its statements; empty theories and incomplete preferences are allowed.
Define \(G(\Gamma)\) by adding edges \(Y\to X\) for every \(Y\in U\), and \(X\to Z\) for every \(Z\in W\), for each statement. Promise that \(G(\Gamma_t)\) is acyclic for every supported type.
A society is given by its support: the list \(T\) of the \(\tau\) types with positive mass, each with its mass \(\mu_t\) as a binary rational, with \(\sum_{t\in T}\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types.
Given also a binary rational \(q\in[0,1]\), define \(M=\sum_{t\in T:\,\Gamma_t\text{ consistent}}\mu_t\). Let \(L\) be the total input bit length, including the explicitly listed theories, masses, and threshold; state running times in \(m,\tau,L\).
Is deciding whether \(M\ge q\) in \(\mathrm{P}\) or \(\mathrm{NP}\)-hard, and can \(M\) be computed exactly in polynomial time?
Known discrete result: with acyclic \(G(\Gamma)\), consistency is equivalent to local consistency: for every outcome and variable, the value comparisons whose conditions that outcome satisfies form an acyclic relation. For Boolean variables, local consistency can be checked in time \(O(|\Gamma|^2m)\).
The established result concerns individual theories; it does not state a complexity result for the distributional mass problem.
The decision problem is in \(\mathrm{P}\), and \(M\) can be computed exactly in polynomial time. The crucial premise is that the support is explicitly listed: only the \(\tau\) supplied theories need to be checked.
Write \(n_t=|\Gamma_t|\). We use the supplied theorem: because \(G(\Gamma_t)\) is acyclic, \(\Gamma_t\) is consistent exactly when it is locally consistent.
For Boolean variables, local inconsistency has a concrete witness: two statements about the same variable \(X\), with opposite preferences, whose conditions are compatible.
To justify this characterization:
Consequently, examine every pair of statements in \(\Gamma_t\). Reject the theory if a pair concerns the same variable, specifies opposite comparisons, and has compatible conditions. Otherwise accept it. By the supplied theorem and the preceding characterization, this procedure decides consistency.
The supplied running-time bound gives total consistency-checking time
\[
O\!\left(m\sum_{t\in T}n_t^2\right).
\]
The sets \(W\) need not enter this local test; their effect is covered by the promised acyclicity and the supplied equivalence theorem.
Represent the input rationals as
\[
\mu_t=\frac{p_t}{d_t},
\qquad
q=\frac{a}{b},
\]
with nonnegative numerators and positive denominators. This also covers dyadic binary rationals.
Let \(c_t\in\{0,1\}\) indicate whether the consistency test accepts \(\Gamma_t\). Define the common denominator
\[
D=b\prod_{t\in T}d_t
\]
and integers
\[
N=\sum_{t\in T}c_t p_t\frac{D}{d_t},
\qquad
Q=a\frac{D}{b}.
\]
Every displayed division is exact. Direct substitution gives
\[
M=\frac{N}{D},
\qquad
M\ge q\quad\Longleftrightarrow\quad N\ge Q.
\]
Thus the algorithm outputs \(N/D\) as the exact mass and compares two integers to answer the decision question. If a reduced fraction is required, divide \(N,D\) by their greatest common divisor.
The bit length of \(D\) is at most
\[
1+\log_2 b+\sum_{t\in T}\log_2 d_t=O(L).
\]
Moreover, nonnegativity, the normalization of the masses, and the threshold bounds imply
\[
0\le N\le D,
\qquad
0\le Q\le D.
\]
Each summand and partial sum used to construct \(N\) is likewise at most \(D\). Therefore all arithmetic uses integers with \(O(L)\) bits. Schoolbook multiplication and division give an arithmetic bound of \(O((\tau+1)L^2)\) bit operations; fraction reduction is also polynomial-time.
Combining the supplied consistency bound with exact arithmetic gives
\[
O\!\left(
L+m\sum_{t\in T}n_t^2+(\tau+1)L^2
\right).
\]
For a bound polynomial solely in the input length, discard variables occurring in no statement and relabel the remaining variables. This preserves local consistency: every assignment to the occurring variables extends to an outcome, and absent variables receive no comparisons. It also preserves acyclicity, so the supplied theorem still applies.
At most \(\min\{m,L\}\) variables occur, and \(\sum_t n_t\le L\). Including polynomial-time relabeling, the resulting bound is
\[
O\!\left((\min\{m,L\}+\tau+1)L^2\right)
\subseteq O(L^3).
\]
Hence both exact mass computation and threshold decision are polynomial-time. In particular, the decision problem could be \(\mathrm{NP}\)-hard under polynomial-time many-one reductions only if \(\mathrm{P}=\mathrm{NP}\).
⟨structured verdict parsed — rendered above⟩
The prover’s conclusion is correct: the threshold problem is in \(\mathrm{P}\), and the exact mass can be computed in polynomial time. The argument resolves both requested questions. No major or minor mathematical issues were found.
The theorem used is precisely the supplied equivalence: for a theory whose graph \(G(\Gamma)\) is acyclic, global consistency is equivalent to local consistency.
Its hypothesis holds for every supported theory by the input promise. The prover applies it separately to each explicitly supplied theory, without assuming any additional theorem about distributions. This is valid.
The pairwise characterization is correct.
Because comparisons are between distinct Boolean values, the only possible directed comparisons for a variable are \(0>1\) and \(1>0\). Such a relation is cyclic exactly when both occur.
Consequently, a local inconsistency exists exactly when two statements:
The compatibility criterion for the conditions is also correct: two partial assignments have a common extension exactly when they agree on their shared domain. The prover explicitly justifies the sufficient direction by extending their union.
Thus checking all qualifying pairs decides local consistency. Empty theories and theories with no conflicting pair are handled correctly: the test accepts them, and the supplied theorem yields consistency.
The omission of \(W\) from the pairwise test is justified. Local consistency concerns the conditioned value comparisons; the supplied equivalence accounts for the remaining semantics under the promised graph acyclicity.
For \(n_t=|\Gamma_t|\), there are \(O(n_t^2)\) pairs, and checking compatibility costs at most \(O(m)\) per pair under the supplied bound. Summing over the explicitly listed support gives
\[ O\!\left(m\sum_{t\in T}n_t^2\right). \]
The additional \(O(L)\) term in the overall bound accommodates reading the input, including theories for which the pairwise work is empty.
No enumeration of outcomes or unsupported types is required.
The chosen common denominator
\[ D=b\prod_{t\in T}d_t \]
is positive and divisible by every denominator used. Therefore the divisions defining \(N\) and \(Q\) are exact.
Substitution verifies both identities:
\[ \frac ND=\sum_{t\in T}c_t\frac{p_t}{d_t}=M, \qquad \frac QD=\frac ab=q. \]
Since \(D>0\), the equivalence \(M\ge q\Longleftrightarrow N\ge Q\) follows. An unreduced fraction is an exact representation of the mass, and the optional greatest-common-divisor reduction is valid.
The endpoint cases \(M=0\), \(M=1\), \(q=0\), and \(q=1\) are included without exceptions.
The denominator-size estimate is valid:
\[ \operatorname{bits}(D) \le 1+\log_2 b+\sum_{t\in T}\log_2 d_t =O(L). \]
Normalization and nonnegativity give \(0\le M\le1\), hence \(0\le N\le D\). Likewise, \(q\in[0,1]\) gives \(0\le Q\le D\). Every included summand and partial sum is nonnegative and bounded by \(N\), so the stated size control is correct.
The construction requires \(O(\tau+1)\) integer arithmetic operations on integers with \(O(L)\) bits. Schoolbook multiplication and division therefore support the claimed \(O((\tau+1)L^2)\) bit-operation bound. Fraction reduction remains polynomial-time.
Removing variables occurring in no statement is valid. Here occurrence includes membership in conditions and in the sets \(W\), as well as being a compared variable.
Every assignment to retained variables extends to a full outcome, and removed variables contribute no local comparisons. Local consistency is therefore preserved. Graph acyclicity is also preserved, so the supplied theorem remains applicable.
The bounds on the number of retained variables and explicitly listed statements yield
\[ O\!\left((\min\{m,L\}+\tau+1)L^2\right)\subseteq O(L^3). \]
The explicitly listed support also ensures \(\tau=O(L)\). Polynomial-time relabeling fits within this bound.
Both the exact computation and threshold decision claims follow. The final qualification concerning \(\mathrm{NP}\)-hardness is correct: a problem in \(\mathrm{P}\) could be \(\mathrm{NP}\)-hard under polynomial-time many-one reductions only if \(\mathrm{P}=\mathrm{NP}\).
No repair or additional mathematical 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.