d4-conf-atal-2015-0217 (d4-conf-atal-2015-0217)

Given an agenda \(\Phi\) whose formula-incidence graph has treewidth \(w\), decide whether, for every distribution \(\mu\) over complete consistent judgment types \(J\in\mathcal{J}(\Phi)\), the set \(\{\varphi\in\Phi: \sum_{J\ni\varphi}\mu_J>1/2\}\) is consistent.

Let \(\Phi=\{\varphi_1,\neg\varphi_1,\ldots,\varphi_m,\neg\varphi_m\}\) be a finite nonempty agenda, with distinct CNF formulas \(\varphi_i\), no doubly negated formulas, and no additional integrity constraints. Its formula-incidence graph has vertices consisting of the propositional variables and the \(m\) positive formulas, with an edge whenever a variable occurs in a formula; let \(w\) be its treewidth.
A judgment type chooses exactly one formula from each complementary pair and is consistent, meaning that its chosen formulas are jointly satisfiable. Write \(\mathcal J(\Phi)\) for all such types.
A society is given by its support: the list of the \(\tau\) types with positive mass, each with its mass as a binary rational. Here \(\tau\) is the support size, not the number of possible types; masses sum to \(1\).
Define \(M(\mu)=\{\psi\in\Phi:\sum_{J\ni\psi}\mu_J>1/2\}\); at equality neither member of the complementary pair is accepted, and the output need not be complete.
The decision input is only the agenda: determine whether \(M(\mu)\) is consistent for every rational-mass society, with unrestricted support. Let \(L\) denote encoding bit length; state agenda-decision runtimes in \(m,L,w\), and runtimes involving an explicitly represented society additionally in \(\tau\).

Is this universal rational-mass majority-safety problem in \(\mathrm P\), or is it \(\mathrm{NP}\)-hard?

For finite societies, majority agenda safety is \(\Pi_2^{\mathrm P}\)-complete; parameterization by formula-incidence treewidth is \(\mathrm{para}\text{-}\Pi_2^{\mathrm P}\)-complete, with hardness claimed already at treewidth \(1\). [Source](https://pure.uva.nl/ws/files/42895111/p127_endriss.pdf)
No separate complexity classification for exactly this universal rational-mass formulation was located.

Result

The problem is \(\Pi_2^{\mathrm P}\)-complete, already when the formula-incidence treewidth is \(w=1\). In particular, it is \(\mathrm{NP}\)-hard. Hardness for \(\mathrm{NP}\) holds even with \(m=3\) complementary pairs.

The proof below uses a direct reduction satisfying the stated CNF and graph requirements.

1. Rational masses and finite electorates are equivalent

Let a rational-mass society have support \(J_1,\ldots,J_\tau\), with masses \(\mu_1,\ldots,\mu_\tau\). Choose a common positive denominator \(D\), and write \(\mu_j=a_j/D\). Since the masses sum to \(1\), \(\sum_j a_j=D\).

Construct a finite electorate containing \(a_j\) copies of \(J_j\). For every agenda formula \(\psi\), its fraction of supporters is exactly

\(D^{-1}\sum_{j:\psi\in J_j}a_j=\sum_{j:\psi\in J_j}\mu_j.\)

Thus both representations produce exactly the same majority output, including ties. Conversely, every finite electorate yields a rational-mass society by recording its empirical frequencies.

Consequently, universal safety for rational masses is equivalent to safety for all finite electorate sizes. This observation does not require the denominator \(D\) to be polynomially bounded.

2. Every unsafe agenda has a three-type witness

A subset \(S\subseteq\Phi\) is *minimally inconsistent* if it is inconsistent and every proper subset is consistent. The *median property* states that every minimally inconsistent subset has size at most \(2\).

We prove the following equivalences:

• Every rational-mass society has a consistent majority output.
• The agenda has the median property.
• Every society consisting of three judgment types, each with mass \(1/3\), has a consistent majority output.

The median property implies universal safety

Suppose \(M(\mu)\) is inconsistent. Since the agenda is finite, it contains a minimally inconsistent subset \(S\).

No inconsistent singleton can belong to \(M(\mu)\): an unsatisfiable formula belongs to no consistent judgment type and therefore has support \(0\).

Nor can an inconsistent pair \(\{\psi,\chi\}\) belong to \(M(\mu)\). Define events \(A=\{J:\psi\in J\}\) and \(B=\{J:\chi\in J\}\). Both have mass greater than \(1/2\), so

\(\mu(A\cap B)\geq\mu(A)+\mu(B)-1>0.\)

Hence some consistent type contains both formulas, contradicting their joint inconsistency.

Thus \(S\) has size at least \(3\), contradicting the median property.

Failure of the median property produces three equal masses

Suppose \(S\) is minimally inconsistent and \(|S|\geq3\). Partition it into three nonempty, disjoint sets:

\(S=S_1\mathbin{\dot\cup}S_2\mathbin{\dot\cup}S_3.\)

For each \(i\in\{1,2,3\}\), minimality makes \(S\setminus S_i\) consistent. Choose a satisfying assignment \(a_i\), and let \(J_i\) be the complete judgment type induced by \(a_i\).

Every formula in \(S_i\) belongs to both \(J_j\) with \(j\neq i\). Therefore the society assigning mass \(1/3\) to each \(J_i\) accepts every formula in \(S\). Its majority output is inconsistent.

These three types are distinct: if two coincided, their common consistent type would determine the entire three-voter majority output, contradicting its inconsistency.

This proves all three equivalences. It also shows that unrestricted support introduces no larger necessary witness: every unsafe agenda has a witness with support size exactly \(3\).

For \(m\leq2\), safety follows immediately: a minimally inconsistent set of size at least \(3\) cannot contain complementary formulas, and therefore would require at least three complementary pairs.

3. Membership in \(\Pi_2^{\mathrm P}\)

Let \(V\) be the agenda’s variable set. Every assignment \(a:V\to\{0,1\}\) induces a consistent complete type by choosing \(\varphi_i\) precisely when \(\varphi_i(a)=1\).

For three assignments \(a_1,a_2,a_3\), define

\(b_i=\operatorname{maj}\bigl(\varphi_i(a_1),\varphi_i(a_2),\varphi_i(a_3)\bigr).\)

Their majority output is inconsistent precisely when no assignment realizes the truth vector \((b_1,\ldots,b_m)\). By the preceding section, unsafety is therefore equivalent to

\(\exists a_1,a_2,a_3\ \forall a\quad \bigvee_{i=1}^{m}\bigl[\varphi_i(a)\neq b_i\bigr].\)

Each assignment has polynomial encoding length, and the predicate can be evaluated in polynomial time by evaluating the CNF formulas. Thus unsafety belongs to \(\Sigma_2^{\mathrm P}\), and safety belongs to \(\Pi_2^{\mathrm P}\).

4. Direct hardness at formula-incidence treewidth \(1\)

We reduce from the \(\Pi_2^{\mathrm P}\)-complete problem of deciding whether

\(\forall X\ \exists Y\ \theta(X,Y)\)

is true, where \(X,Y\) are disjoint variable sets and \(\theta\) is a \(3\)-CNF formula. This standard source problem remains complete under stronger restrictions; see [Döcker, Dorn, Linz and Semple](https://arxiv.org/abs/1908.05361).

Write \(\theta=\bigwedge_{j=1}^{s}C_j\). Introduce fresh variables \(p,q,r\), and construct the CNF formula

\(F=r\wedge\bigwedge_{j=1}^{s}(C_j\vee p\vee q).\)

Its semantics are

\(F\equiv r\wedge\bigl(\theta(X,Y)\vee p\vee q\bigr).\)

The agenda’s positive formulas are

\(\{x:x\in X\}\cup\{p,q,F\}.\)

Each atom is a unit-clause CNF. These formulas are syntactically distinct, since \(F\) contains the fresh variable \(r\). Adding their single negations gives an agenda of the required form, with \(m=|X|+3\). The construction has polynomial encoding length.

If the quantified formula is true, the agenda is safe

We show that every truth pattern on the positive formulas is realizable.

Fix arbitrary values for \(X,p,q\), and a desired truth value for \(F\).

• To realize \(F=0\), set \(r=0\), and assign \(Y\) arbitrarily.
• To realize \(F=1\), use the hypothesis to choose \(Y\) satisfying \(\theta(X,Y)\), and set \(r=1\).

Thus every complete judgment pattern is consistent.

Every majority output is complement-free, because the support masses of complementary formulas sum to \(1\), so they cannot both exceed \(1/2\). Complete that output arbitrarily to a judgment pattern. Since every such pattern is realizable, the majority output is consistent.

If the quantified formula is false, the agenda is unsafe

There is an assignment \(\alpha\) to \(X\) such that \(\theta(\alpha,Y)\) is unsatisfiable.

Construct three assignments, all agreeing with \(\alpha\) on \(X\), with arbitrary values for \(Y\), and with the following values:

| Assignment | \(p\) | \(q\) | \(r\) | \(F\) |
|---|---|---|---|---|
| First | \(0\) | \(1\) | \(1\) | \(1\) |
| Second | \(1\) | \(0\) | \(1\) | \(1\) |
| Third | \(0\) | \(0\) | \(0\) | \(0\) |

The displayed values of \(F\) follow directly from its defining CNF. Their induced types are therefore consistent.

With equal masses \(1/3\), the majority accepts the literals specifying \(\alpha\), together with \(\neg p,\neg q,F\). Any satisfying assignment for this output would have \(X=\alpha\), \(p=q=0\), and \(F=1\). The definition of \(F\) would then require \(\theta(\alpha,Y)=1\), which is impossible.

Therefore the agenda is unsafe.

The graph has treewidth exactly \(1\)

In the formula-incidence graph, \(F\) is adjacent to its occurring variables. Every other positive formula is an atom and consequently has exactly one incident edge, connecting its formula vertex to its variable vertex.

The graph is therefore a forest: a star centered at \(F\), with atom-formula leaves attached to some variable vertices, and possibly separate atom-variable edges. It has an edge, including the edge between \(F\) and \(r\), so its treewidth is exactly \(1\).

We have proved

\(\forall X\exists Y\,\theta(X,Y)\text{ is true}\quad\Longleftrightarrow\quad\Phi\text{ is universally majority-safe}.\)

Together with membership, this establishes \(\Pi_2^{\mathrm P}\)-completeness already at \(w=1\), and hence \(\mathrm{para}\text{-}\Pi_2^{\mathrm P}\)-completeness parameterized by \(w\). This independently verifies the treewidth claim in [Endriss, de Haan and Szeider, Proposition 9](https://pure.uva.nl/ws/files/42895111/p127_endriss.pdf).

Taking \(X=\varnothing\) specializes the construction to a reduction from CNF satisfiability to safety. It has \(m=3\) and \(w=1\), proving the asserted \(\mathrm{NP}\)-hardness with both parameters fixed.

5. Explicit runtime bounds

For agenda-only inputs, let \(L\) denote their encoding length. Let \(n\) be the number of occurring variables, so \(n\leq L\).

Agenda-only decision

Represent a type by its truth vector in \(\{0,1\}^{m}\). Enumerating all assignments builds a table of realizable vectors in time \(O(2^nL)\). By Section 2, safety is equivalent to closure of that table under coordinatewise majority of three vectors. Checking all triples costs \(O(m2^{3m})\).

Thus an unconditional deterministic bound, stated using the requested parameters, is

\(T_{\mathrm{agenda}}(m,L,w)=O(2^LL+m2^{3m}).\)

This bound is uniform in \(w\).

Alternatively, determine realizability of each of the \(2^m\) vectors by a satisfiability query for its signed agenda conjunction. These queries have encoding length \(O(L)\). The resulting algorithm uses at most \(2^m\) SAT queries and has additional work

\(2^{O(m)}\operatorname{poly}(L).\)

The hardness result rules out deterministic runtimes \(f(w)L^{O(1)}\), or even \(f(m,w)L^{O(1)}\), unless \(\mathrm P=\mathrm{NP}\). There is no society input here, so no \(\tau\) appears in these bounds.

An explicitly represented society

Here let \(L\) denote the total agenda-and-society encoding length, including rational masses, and let \(\tau\) be the given support size.

Using exact rational arithmetic with ordinary quadratic-time integer arithmetic, all marginal masses and strict-majority comparisons can be computed within

\(T_{\mathrm{majority}}(m,L,w,\tau)=O(m\tau L^2).\)

Indeed, intermediate denominators divide the product of input denominators, whose bit length is \(O(L)\).

Checking consistency of the resulting output requires one SAT query of encoding length \(O(L)\). Without an oracle, exhaustive assignment enumeration gives

\(T_{\mathrm{society}}(m,L,w,\tau)=O(m\tau L^2+2^LL).\)

These bounds are also uniform in \(w\). Computing the output is polynomial; checking its consistency remains \(\mathrm{NP}\)-complete even with \(m=3\), \(w=1\), and \(\tau=3\): use the construction above with \(X=\varnothing\) and the three displayed types. Their majority output is satisfiable exactly when \(\theta\) is satisfiable.

⟨structured verdict parsed — rendered above⟩

Verdict

The prover resolves the assigned problem. The argument establishes \(\Pi_2^{\mathrm P}\)-completeness of universal rational-mass majority safety, already at formula-incidence treewidth \(w=1\). Its separate reduction establishes \(\mathrm{NP}\)-hardness with \(m=3\) and \(w=1\).

I found no mathematical errors or gaps requiring repair. The runtime bounds are valid, although deliberately coarse.

Step-by-step verification

1. Rational masses and finite electorates

This equivalence is correct.

Because the support is finite and every mass is rational, a common positive denominator \(D\) exists. The resulting numerators are positive integers summing to \(D\), so the constructed electorate is nonempty and consists entirely of consistent judgment types.

Every formula has exactly the same support fraction in both representations. Consequently, strict majorities and ties are preserved. Conversely, empirical frequencies from any nonempty finite electorate give rational masses.

The potentially exponential size of this electorate does not invalidate the equivalence: the prover uses it as a semantic equivalence, not as a polynomial-time reduction.

2. Median property and three-type witnesses

Both directions are correct.

Median property implies safety. An inconsistent majority output contains a minimally inconsistent subset because the agenda is finite. An unsatisfiable singleton cannot receive positive support from consistent types. For an inconsistent pair, the displayed inequality correctly shows that two support masses exceeding \(1/2\) force positive mass on their intersection. Since the society has finite support, some consistent type would then contain both formulas, a contradiction.

This argument covers incomplete majority outputs and ties; completeness is not assumed.

Failure of the median property implies a three-type witness. A minimally inconsistent set of size at least three can be partitioned into three nonempty parts. Each complement of a part is a proper subset and hence satisfiable. The types induced by the chosen satisfying assignments are complete and consistent.

Every member of the minimally inconsistent set occurs in at least two of these types, giving support at least \(2/3\). Thus the majority output contains the entire inconsistent set.

The distinctness argument is also valid. If two of the three complete types coincided, their common type would be the entire majority output. That output would be consistent, contradicting the preceding construction.

The stated equivalences follow, including the claim that every unsafe agenda has a witness with support size exactly three.

Small agendas. The assertion for \(m\leq2\) is correct. A minimally inconsistent set of size at least three cannot contain a complementary pair, because that pair would already be a proper inconsistent subset. Such a set therefore requires at least three complementary pairs.

3. Membership in \(\Pi_2^{\mathrm P}\)

The quantified characterization is correct.

Every consistent complete type is realized by an assignment satisfying its chosen formulas. Conversely, each assignment induces such a type. Thus quantifying over assignments covers all judgment types needed for the three-type characterization.

Three voters have no ties, so their majority output specifies a complete truth vector on the positive formulas. This output is inconsistent exactly when every assignment disagrees with that vector in at least one coordinate.

The displayed existential–universal predicate therefore characterizes unsafety. The assignments have polynomial length, and CNF evaluation takes polynomial time. This establishes unsafety in \(\Sigma_2^{\mathrm P}\) and safety in \(\Pi_2^{\mathrm P}\).

4. Hardness reduction

Source problem. The cited source supports the precise completeness claim used: truth of \(\forall X\exists Y\,\theta(X,Y)\) with a \(3\)-CNF matrix is \(\Pi_2^{\mathrm P}\)-complete, even under additional restrictions. The reduction does not require those restrictions. [Döcker, Dorn, Linz and Semple](https://arxiv.org/abs/1908.05361)

Construction. The formula \(F\) is CNF, has polynomial encoding length, and has the stated semantics. The fresh variable \(r\) ensures that \(F\) is syntactically distinct from every atomic positive formula. The agenda satisfies the stipulated syntactic requirements.

True quantified instance. For every assignment to \(X,p,q\), setting \(r=0\) realizes \(F=0\). The source hypothesis supplies an assignment to \(Y\) satisfying the matrix for that particular \(X\), allowing \(F=1\) with \(r=1\). Thus every complete truth pattern is realizable.

Every strict-majority output is complement-free. Completing it arbitrarily and using realizability therefore proves consistency, including when the original output contains ties.

False quantified instance. The fixed assignment \(\alpha\) has no satisfying extension to \(Y\). The three rows of the table evaluate \(F\) correctly: the first two satisfy every augmented clause through \(q\) or \(p\), respectively, while the third falsifies the unit conjunct \(r\).

Their majority fixes \(X=\alpha\), accepts \(\neg p,\neg q,F\), and therefore requires a satisfying extension of \(\theta(\alpha,Y)\). None exists. The reduction has the correct yes-instance orientation: quantified truth corresponds to safety.

Treewidth. The described incidence graph is a forest. Only \(F\) can have multiple variable neighbors; every other formula vertex is a leaf. The edge incident with \(r\) ensures that the graph has treewidth exactly one.

The resulting parameterized completeness claim is valid under the standard definition of \(\mathrm{para}\text{-}\Pi_2^{\mathrm P}\) and fpt reductions. It also agrees with the cited Proposition 9. [Endriss, de Haan and Szeider](https://pure.uva.nl/ws/files/42895111/p127_endriss.pdf)

Fixed agenda size. Taking \(X=\varnothing\) is a valid separate SAT reduction. Safety holds exactly when the CNF matrix is satisfiable, with three positive formulas and treewidth one. This establishes the stronger fixed-parameter \(\mathrm{NP}\)-hardness claim.

5. Runtime bounds and explicitly represented societies

The agenda-only algorithms are valid.

Assignment enumeration identifies all realizable truth vectors. Closure under coordinatewise majority of triples is exactly the characterization already proved. There are at most \(2^{3m}\) triples, and each requires \(O(m)\) coordinate work and table access with a suitable representation.

Consequently, the stated deterministic bound
\[ O(2^L L+m2^{3m}) \]
is valid using \(n\leq L\). The alternative algorithm has at most \(2^m\) satisfiability queries and the stated exponential-in-\(m\) additional work. Signed conjunctions have linear-size propositional representations; negated CNFs need not be expanded distributively.

The fixed-\(m,w\) SAT reduction correctly excludes the proposed deterministic parameterized runtimes unless \(\mathrm P=\mathrm{NP}\).

For an explicit society, exact rational arithmetic is justified: products of the input denominators have total bit length \(O(L)\), and marginal sums have polynomially bounded intermediate bit lengths. The bound \(O(m\tau L^2)\) is a valid conservative bound using quadratic integer arithmetic.

Checking the resulting output requires a satisfiability query, or the stated exhaustive enumeration. Finally, the fixed three-type construction with \(X=\varnothing\) gives a valid society whose majority output is consistent exactly when the source CNF is satisfiable. Together with a satisfying-assignment certificate, this supports the claimed \(\mathrm{NP}\)-completeness.

Issues and repair feedback

No repair is required. The proof addresses unrestricted rational support, strict-majority ties, agenda-only input, the specified incidence graph, and all requested runtime parameters.

⟨structured verdict parsed — rendered above⟩