Answer: \(\mathrm{NP}\)-complete, even for \(\tau=1\), \(\mu_1=1\), \(\theta=\tfrac12\), and a total preorder with three indifference classes.
Theorem 4 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateLet T = (A, R) be a PBAT and a ∈A. Deciding whether a is a credulous conclusion of T is NP-hard. Proof We prove the claim by a reduction from 3SAT. Let S = {c1, . . . cn} be a 3SAT theory on a set of clauses c1, . . . cn. From S we construct a PBAT ST = (A, R).
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite support of PBAT types \(T_t=(A,C_t,\succeq_t)\) over a shared argument set \(A\), a common queried argument \(a\in A\), binary-rational masses \(\mu_t\) summing to \(1\), and a rational threshold \(\theta\), decide whether \(\sum_t \mu_t \mathbf{1}[a\text{ belongs to some stable extension of }T_t]\ge\theta\).
A society is given by its support: a list of \(\tau\) distinct PBAT types \(T_t=(A,C_t,\succeq_t)\), each with positive binary-rational mass \(\mu_t\), where \(\sum_{t=1}^{\tau}\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types.
The shared argument set \(A\) is finite and nonempty, with \(m=|A|\). Each explicitly encoded relation \(C_t\subseteq A\times A\) is symmetric and irreflexive; each explicitly encoded \(\succeq_t\) is a partial preorder, allowing indifference and incomparability.
Define \(x\succ_t y\) by \(x\succeq_t y\) and \(y\not\succeq_t x\), and define the attack relation by \((x,y)\in R_t\) exactly when \((x,y)\in C_t\) and \(y\not\succ_t x\). Use Dung stable semantics on \((A,R_t)\).
Given a common queried argument \(a\in A\) and a binary-rational threshold \(\theta\in\mathbb{Q}\), decide whether \(\sum_{t=1}^{\tau}\mu_t\mathbf{1}[\exists E\text{ stable in }(A,R_t):a\in E]\geq\theta\). Let \(L\) be the total input bit length; state running times in \(m,\tau,L\).
Is this mass-threshold decision problem solvable in polynomial time in \(m,\tau,L\), or is it NP-hard?
Discrete credulous acceptance for PBATs is NP-hard, whereas computing one stable extension takes polynomial time. [Source](https://helios2.mi.parisdescartes.fr/~moraitis/webpapers/Moraitis-ECAI08.pdf)
No result settling this exact explicitly supported mass-threshold problem was located.
The problem is \(\mathrm{NP}\)-complete. Hardness holds even when \(\tau=1\), \(\mu_1=1\), \(\theta=\tfrac12\), and the preference relation is a total preorder with three indifference classes. Consequently, a polynomial-time algorithm in \(m,\tau,L\) would imply \(\mathrm{P}=\mathrm{NP}\).
The proof below establishes this directly for the specified encoding and attack definition.
For an attack relation \(R\), a set \(E\subseteq A\) is stable precisely when:
With indexed Boolean tables for \(C_t\) and \(\succeq_t\), the attack relation is computed using
\((x,y)\in R_t\) if and only if \((x,y)\in C_t\) and \(\neg(y\succeq_t x\ \land\ \neg(x\succeq_t y))\).
Thus constructing \(R_t\), checking stability of a proposed \(E\), and checking \(a\in E\) require \(O(m^2)\) Boolean operations per type.
Define the set of accepting types by
\(B=\{t:\exists E\text{ stable in }(A,R_t),\ a\in E\}\).
A certificate consists of a subset \(S\subseteq\{1,\ldots,\tau\}\) and, for each \(t\in S\), an \(m\)-bit description of a stable extension \(E_t\) containing \(a\). The verifier checks these extensions and the inequality
\(\sum_{t\in S}\mu_t\geq\theta\).
Soundness. Every verified type belongs to \(B\), so \(S\subseteq B\). Since all masses are positive,
\(\sum_{t\in B}\mu_t\geq\sum_{t\in S}\mu_t\geq\theta\).
Therefore an accepted certificate implies a yes-instance.
Completeness. For a yes-instance, choose \(S=B\) and one witnessing extension for each accepting type. This certificate passes every check.
The certificate uses at most \(\tau(m+1)\) bits. Since the support and argument set are explicit, this is polynomial in the input length.
Exact rational arithmetic also takes polynomial time. Write each selected mass as \(p_t/q_t\), with \(q_t>0\). An unreduced common denominator divides \(\prod_{t\in S}q_t\), whose bit length is \(O(L)\). Every partial sum lies in \([0,1]\), so its numerator also has \(O(L)\) bits. Schoolbook arithmetic therefore gives the conservative verification bound
\(O\!\left(L+\tau m^2+(\tau+1)L^2\right)\),
using constant-time indexed Boolean access and charging for integer arithmetic at bit cost.
The cases \(\theta\leq0\) and \(\theta>1\) are immediately yes and no, respectively. Hence the problem belongs to \(\mathrm{NP}\).
Reduce from \(\mathrm{3SAT}\). Let
\(\varphi=\bigwedge_{j=1}^{q}D_j\)
have variables \(x_1,\ldots,x_n\). Introduce distinct arguments
\(A=\{x_i^+,x_i^-:1\leq i\leq n\}\cup\{c_j:1\leq j\leq q\}\cup\{a\}\).
Here \(x_i^+\) represents \(x_i\), and \(x_i^-\) represents \(\neg x_i\). Write \(\ell(\lambda)\) for the argument representing a literal \(\lambda\).
Define \(C\) by including both orientations of exactly these unordered pairs:
All pairs contain distinct arguments, so \(C\) is symmetric and irreflexive.
Give literal arguments rank \(2\), clause arguments rank \(1\), and \(a\) rank \(0\). Define
\(u\succeq v\) if and only if \(r(u)\geq r(v)\).
This relation is reflexive and transitive because the numerical order is reflexive and transitive. It is total, with indifference exactly within each rank. Its strict part satisfies
\(u\succ v\) if and only if \(r(u)>r(v)\).
Under the task’s attack definition, the attacks are therefore exactly:
In particular, clauses do not attack literals, and \(a\) does not attack clauses.
Suppose \(v\) satisfies \(\varphi\). Let \(M_v\) contain exactly the literal argument made true by \(v\) for each variable, and put \(E=M_v\cup\{a\}\).
This set is conflict-free: it contains no complementary literal pair and no clause argument.
Every omitted literal argument is attacked by its selected complement. Every clause argument \(c_j\) is attacked by a selected literal because \(v\) satisfies \(D_j\). These are all arguments outside \(E\). Thus \(E\) is stable and contains \(a\).
Conversely, suppose \(E\) is stable and contains \(a\).
Since every \(c_j\) attacks \(a\), conflict-freeness excludes all clause arguments from \(E\). Complementary literals attack each other, so \(E\) contains at most one of \(x_i^+,x_i^-\).
It also contains at least one. If both were omitted, stability would require an argument of \(E\) attacking \(x_i^+\). Its only attacker is \(x_i^-\), which was also omitted. This is impossible.
Hence \(E\) selects exactly one literal per variable, defining an assignment \(v\). Each omitted \(c_j\) must be attacked by \(E\). Its attackers are precisely the literal arguments occurring in \(D_j\), so \(D_j\) has a selected, true literal. Therefore \(v\) satisfies every clause.
We have proved
\(\varphi\text{ is satisfiable}\ \Longleftrightarrow\ \exists E\text{ stable with }a\in E\).
Use this PBAT as the sole supported type, with \(\mu_1=1\) and \(\theta=\tfrac12\). The queried mass is either \(0\) or \(1\), so the threshold inequality holds exactly when \(\varphi\) is satisfiable.
Here \(m=2n+q+1\). Both relations can be explicitly encoded with \(O(m^2\log(m+2))\) bits and constructed in polynomial time. The singleton support satisfies the distinctness requirement, and its positive mass sums to \(1\). This proves \(\mathrm{NP}\)-hardness under polynomial-time many-one reductions.
A deterministic exhaustive algorithm enumerates all subsets containing \(a\) separately for each supported type, checks stability, and then sums the accepting masses. Its running time is
\(O\!\left(L+\tau\,2^m m^2+(\tau+1)L^2\right)\)
under the same computational conventions. It processes only the \(\tau\) explicitly listed types.
Finding an arbitrary stable extension does not resolve the queried acceptance condition. In this reduction, every assignment \(v\) yields a stable extension: select its true literal arguments, include exactly the clause arguments for clauses it leaves unsatisfied, and include \(a\) exactly when no clause is unsatisfied. Conflict-freeness follows from these choices; omitted literals are attacked by their complements, omitted clauses by true literals, and an omitted \(a\) by an included unsatisfied clause. This extension contains \(a\) precisely when \(v\) satisfies \(\varphi\).
This explains why the classification is compatible with the distinction between extension finding and credulous acceptance emphasized in the [cited paper, Section 5](https://helios2.mi.parisdescartes.fr/~moraitis/webpapers/Moraitis-ECAI08.pdf).
⟨structured verdict parsed — rendered above⟩
The output establishes NP-completeness of the explicitly supported mass-threshold problem. The reduction and NP-membership argument are sound. There is one minor omission concerning the stronger claim of exactly three indifference classes: the source instances should explicitly have at least one variable and one clause.
No major issue prevents the complexity classification.
The stated characterization of stability is correct: a set must be conflict-free and attack every argument outside it.
The Boolean formula for the attack relation correctly expands the task’s definition of strict preference:
\(y\succ_t x\) holds exactly when \(y\succeq_t x\) and \(x\not\succeq_t y\).
Thus the displayed test for membership in \(R_t\) is correct, including when arguments are indifferent or incomparable.
With indexed Boolean tables, constructing all attacks and checking the two stability conditions require \(O(m^2)\) Boolean operations per type. Checking whether the queried argument belongs to the proposed extension fits within this bound.
Finding: Correct under the explicitly stated table-access convention.
Certificate size. A membership vector for \(S\) uses \(\tau\) bits, and the proposed extensions use at most \(\tau m\) bits. The claimed bound of \(\tau(m+1)\) bits is valid. Explicit encoding makes this polynomial in \(L\).
Soundness. Each verified witness establishes that its type belongs to \(B\). Therefore \(S\subseteq B\). Positivity of the masses justifies the comparison between the selected mass and the full accepting mass. There is no need to certify that omitted types reject the query.
Completeness. Choosing \(S=B\), with one witnessing extension per accepting type, is valid. This is an existential certificate construction; the prover need not give a polynomial-time method for finding those witnesses.
Rational arithmetic. The product of selected denominators has bit length \(O(L)\). Using that product as a common denominator, the numerator of each partial sum also has \(O(L)\) bits because the sum lies in \([0,1]\). Comparing the resulting sum with the encoded threshold involves integers of \(O(L)\) bits. The stated conservative schoolbook-arithmetic bound is therefore valid.
Threshold edge cases. The accepting mass always lies in \([0,1]\), so the treatment of \(\theta\leq0\) and \(\theta>1\) is correct. The cases \(\theta=0\) and \(\theta=1\) introduce no certificate problem.
Finding: NP membership is established, with verification time
\(O\!\left(L+\tau m^2+(\tau+1)L^2\right)\) under the stated conventions.
The argument names are distinct, and every conflict pair joins distinct arguments. Including both orientations makes \(C\) symmetric and irreflexive.
The rank-defined preference relation is reflexive, transitive, and total. Its strict part is correctly identified by strict rank comparison.
The attack list follows exactly from the task’s definition:
Finding: The constructed relations satisfy all required hypotheses.
The proposed extension selects one literal per variable and includes the query.
Its conflict-freeness follows from the complete attack list: it contains neither complementary literals nor clause arguments.
Every excluded literal is attacked by its selected complement. Every excluded clause is attacked by a selected literal because the assignment satisfies that clause. These exhaust the excluded arguments.
Finding: This implication is correct.
Every clause argument is excluded because it attacks the included query.
Mutual attacks between complementary literals permit at most one literal per variable. Stability forces at least one: if both were excluded, the positive literal would have no included attacker, since its only attacker is its negative complement.
Consequently, the extension defines a complete assignment. Each excluded clause must be attacked, and its only attackers are its occurring literals. Hence every clause has a selected true literal.
Finding: This implication is correct. The argument also accommodates repeated literals, tautological clauses, and unused variables.
For singleton support, the accepting mass is exactly zero or one. The chosen threshold therefore preserves the satisfiability equivalence.
The singleton type automatically satisfies distinctness, and its mass is positive and normalized. The count \(m=2n+q+1\) is correct. Explicitly encoding both relations within \(O(m^2\log(m+2))\) bits is a valid conservative bound, and construction is polynomial in the source input size.
The standard NP-completeness of 3SAT supplies the source hardness; no PBAT theorem from the cited paper is needed for this reduction.
Finding: The polynomial-time many-one reduction establishes NP-hardness.
Enumerating subsets containing the query, checking stability, and summing masses gives the claimed deterministic upper bound
\(O\!\left(L+\tau 2^m m^2+(\tau+1)L^2\right)\).
The additional construction from an arbitrary assignment is also correct. An included unsatisfied clause has no selected literal attacking it; satisfied clauses are excluded and attacked by selected literals. The query is included exactly when no clause is included, and otherwise an included clause attacks it.
Thus finding an arbitrary extension need not determine whether some extension contains the query.
The attribution is accurate: Section 5 of the [cited paper](https://helios2.mi.parisdescartes.fr/~moraitis/webpapers/Moraitis-ECAI08.pdf) discusses polynomial-time extension finding and NP-hard credulous acceptance. The submitted classification is independently justified by its own proof.
Minor — exactly three indifference classes. The construction has three nonempty indifference classes when \(n\geq1\) and \(q\geq1\), but these restrictions are not stated. For example, an empty conjunction with no variables produces only the argument \(a\), hence only one class.
Minimum clarification: Explicitly specify the standard NP-hard 3SAT source restriction with at least one variable and one clause. This is a routine source-domain clarification; neither direction of the reduction needs repair.
⟨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.