Answer: \(\Sigma_2^p\)-complete, hence \(\mathrm{NP}\)-hard; a polynomial-time algorithm in \(m,\tau,L\) would imply \(\mathrm{P}=\mathrm{NP}\).
Theorem 4 — class: hardness
Given a shared argumentation framework \(\Lambda=\langle A,R\rangle\), an argument \(g\in A\), a rational threshold \(q\in(0,1]\), and a finite support of valid ePCAF profiles \(\Delta_j=\langle A,R,C_j,\succ_j\rangle\) with positive rational masses \(\mu_j\) summing to \(1\), decide whether at least a \(q\)-fraction of the society has \(g\) credulously accepted under complete semantics and the paper's KTV comparison. Equivalently, set \(z_j=1\) iff some \(E\in\mathrm{co}_k(\Delta_j)\) contains \(g\), and decide whether \(\sum_{j=1}^{\tau}\mu_j z_j\ge q\).
Given a finite argumentation framework \(\Lambda=\langle A,R\rangle\), let \(m=|A|\ge1\), and let \(g\in A\). A society is given by its support: a list of \(\tau\ge1\) distinct types \(\Delta_j=\langle A,R,C_j,\succ_j\rangle\) with positive binary rational masses \(\mu_j\) summing to \(1\). Here \(\tau\) is the support size, not the number of possible types.
Each \(C_j\) is an explicitly listed set of constraints \(\varphi\Rightarrow v\) or \(v\Rightarrow\varphi\), where \(v\in\{f,u,t\}\) and \(\varphi\) is a propositional formula over \(A\) using \(\wedge,\vee,\neg,\Rightarrow\); \(C_j\) is promised satisfiable by some three-valued assignment. Evaluate formulas in three-valued Łukasiewicz logic; a constraint is satisfied exactly when its value is \(t\).
Each \(\succ_j\) is an explicitly listed strict partial order on \(A\times\{f,u,t\}\), with \(a^v\) denoting \((a,v)\). For a Dung complete extension \(E\), put \(t(E)=E\), \(f(E)=\{a\in A:\exists b\in E\ (b,a)\in R\}\), and \(u(E)=A\setminus(E\cup f(E))\); these sets assign the arguments their truth values.
Let \(\mathcal F_j\) be the complete extensions satisfying \(C_j\). For distinct \(E,F\in\mathcal F_j\), define \(E\succeq_j F\) iff there is no \(a^v\succ_j b^w\) with \(a\in v(F)\setminus v(E)\) and \(b\in w(E)\setminus w(F)\). Define \(E\triangleright_j F\) iff \(E\succeq_j F\) and \(F\not\succeq_j E\).
The KTV-best complete extensions are \(\mathcal B_j=\{E\in\mathcal F_j:\nexists F\in\mathcal F_j\text{ with }F\triangleright_j E\}\). Set \(z_j=1\) iff some \(E\in\mathcal B_j\) contains \(g\), and \(z_j=0\) otherwise, including when \(\mathcal B_j\) is empty. Given a binary rational \(q\in(0,1]\), decide whether \(\sum_{j=1}^{\tau}\mu_jz_j\ge q\). Let \(L\) be the total input bit length; state running times in \(m,\tau,L\).
Is this mass-threshold credulous-acceptance problem solvable in polynomial time in \(m,\tau,L\), or is it NP-hard?
For a finite, fixed number of agents, both existential and universal agentwise credulous acceptance under complete semantics and KTV comparison are \(\Sigma_2^p\)-complete; single-type acceptance is also \(\Sigma_2^p\)-complete. [Source](https://www.ijcai.org/proceedings/2023/0345.pdf)
No result for exactly the rational-mass threshold problem was identified in the literature search.
The problem is \(\Sigma_2^p\)-complete under polynomial-time many-one reductions, and therefore \(\mathrm{NP}\)-hard. Consequently, a polynomial-time algorithm in \(m,\tau,L\) would imply \(\mathrm{P}=\mathrm{NP}\).
The permitted case \(\tau=1\) already establishes hardness. The rational-mass aggregation also admits a \(\Sigma_2^p\) upper bound, even when the support size varies with the input.
For a subset \(E\subseteq A\), define its defeated set and defended set by
\(f(E)=\{a\in A:\exists b\in E,\ (b,a)\in R\}\),
\(D(E)=\{a\in A:\text{every attacker of }a\text{ belongs to }f(E)\}\).
By the definition of Dung complete semantics, \(E\) is complete exactly when \(E\cap f(E)=\varnothing\) and \(E=D(E)\). These conditions, and the resulting truth-value assignment, can be computed in \(O(m^2)\) time using an attack matrix.
Each explicitly represented constraint can then be evaluated by traversing its formula. Every connective has a fixed three-valued truth table, so the time is linear in the formula representation. Thus membership in \(\mathcal F_j\) is decidable in polynomial time.
For distinct feasible extensions \(E,F\), the test \(E\succeq_j F\) scans the explicitly listed preference pairs and checks the two required set differences. Testing both directions decides \(E\triangleright_j F\) in polynomial time. Identical extensions never strictly dominate one another.
The threshold comparison also uses polynomial-time exact arithmetic. Write \(\mu_j=a_j/b_j\) and \(q=c/d\), with positive integer denominators, and set
\(H=d\prod_{j=1}^{\tau}b_j,\qquad W_j=a_j(H/b_j),\qquad Q=c(H/d)\).
Then, for any subset \(S\subseteq\{1,\ldots,\tau\}\),
\(\sum_{j\in S}\mu_j\ge q\quad\Longleftrightarrow\quad\sum_{j\in S}W_j\ge Q\).
The integers involved have \(O(L)\) bits: the bit length of the product is bounded by the total denominator bit length, and \(\mu_j,q\le1\). Ordinary integer arithmetic therefore performs this comparison in polynomial time; \(O(L^3)\) is a sufficient bound.
We use the characterization of \(\Sigma_2^p\) by an existentially quantified polynomial-length string followed by a universally quantified polynomial-length string, with a polynomial-time predicate.
Existentially choose a subset \(S\subseteq\{1,\ldots,\tau\}\) and an extension \(E_j\subseteq A\) for every \(j\in S\). Require:
The existential data use \(O(\tau(m+1))\) bits. The third condition can be checked by universally quantifying a single pair \((j,F)\), using \(O(\log(\tau+1)+m)\) bits. Invalid indices and indices outside \(S\) impose no condition. Section 1 shows that the resulting predicate is polynomial-time computable.
To prove equivalence with the target decision:
This argument also covers empty feasible or best-extension sets: such a type cannot supply a selected witness.
Therefore the problem belongs to \(\Sigma_2^p\).
Here is a reduction from Boolean satisfiability that does not depend on the cited argumentation hardness theorem.
Let \(\phi\) be a Boolean formula over variables \(x_1,\ldots,x_n\). Construct
\(A=\{g\}\cup\{x_i,y_i:1\le i\le n\}\),
\(R=\{(x_i,y_i),(y_i,x_i):1\le i\le n\}\).
Thus \(g\) is unattacked, and the remaining arguments form disjoint mutually attacking pairs. Use one type, with empty preference order, mass \(\mu_1=1\), and threshold \(q=1\). Its constraints are
\(C_1=\{t\Rightarrow(x_i\vee\neg x_i):1\le i\le n\}\cup\{t\Rightarrow(\neg g\vee\phi)\}\).
Assign \(g=f\), every \(x_i=f\), and every \(y_i=f\). Each \(x_i\vee\neg x_i\) has value \(t\), and \(\neg g\vee\phi\) has value \(t\) because \(\neg g=t\).
In Łukasiewicz logic, \(t\Rightarrow\psi\) has the same value as \(\psi\). Hence this assignment satisfies every constraint, regardless of whether \(\phi\) is Boolean-satisfiable.
The empty preference relation is a strict partial order. With one type, the distinctness requirement is automatic.
Every complete extension contains the unattacked argument \(g\): it is defended by every set, and a complete extension contains every argument it defends.
For each pair \(\{x_i,y_i\}\), a complete extension contains exactly one of the following local choices:
\(\varnothing,\qquad\{x_i\},\qquad\{y_i\}\).
Indeed, selecting both violates conflict-freeness. Selecting neither leaves neither argument defended. Selecting one defends that argument against its sole attacker and does not defend the other. Since there are no attacks between components, arbitrary combinations of these local choices, together with \(g\), are complete.
Their values for \(x_i\) are respectively \(u,t,f\). Moreover,
\(x_i\vee\neg x_i=t\quad\Longleftrightarrow\quad x_i\in\{f,t\}\).
Therefore the first group of constraints eliminates the empty local choices. The surviving extensions correspond bijectively to Boolean assignments: select \(x_i\) when the variable is true and \(y_i\) when it is false.
Because every complete extension assigns \(g=t\), the final constraint is satisfied exactly when \(\phi\) evaluates to \(t\). On Boolean assignments, the specified three-valued connectives agree with their Boolean counterparts. Consequently,
\(\mathcal F_1\ne\varnothing\quad\Longleftrightarrow\quad\phi\text{ is Boolean-satisfiable}\).
Finally, the empty preference order makes both comparison directions hold for every pair of distinct feasible extensions. There is therefore no strict domination, so \(\mathcal B_1=\mathcal F_1\). Every such extension contains \(g\), giving
\(\sum_{j=1}^{\tau}\mu_jz_j\ge q\quad\Longleftrightarrow\quad z_1=1\quad\Longleftrightarrow\quad\phi\text{ is satisfiable}\).
The construction has \(m=2n+1\), \(\tau=1\), and polynomial output bit length. This proves \(\mathrm{NP}\)-hardness while satisfying every input promise.
Theorem 1 of [Alfano, Greco, Parisi, and Trubitsyna, *Preferences and Constraints in Abstract Argumentation*](https://www.ijcai.org/proceedings/2023/0345.pdf) states that credulous acceptance among KTV-best complete extensions of an extended preference-based argumentation framework is \(\Sigma_2^p\)-complete.
Its hypotheses match a restricted instance here: the preference relation is a strict partial order on argument–truth-value pairs, and Definition 9 gives exactly the comparison in the question. Under complete semantics, the source’s defended set equals the extension, so the truth-value assignments also agree.
Map such an instance to one type with \(C_1=\varnothing\), \(\mu_1=1\), and \(q=1\). The empty constraint set satisfies the promise, and the threshold answer equals the source’s single-type credulous-acceptance answer. This is a polynomial-time many-one reduction.
Thus the threshold problem is \(\Sigma_2^p\)-hard. Together with Section 2, it is \(\Sigma_2^p\)-complete.
An exhaustive exact algorithm gives a bound in the requested parameters:
Let \(c_j\) be the formula-representation length for type \(j\), and \(p_j\) its number of listed preference pairs. Feasibility filtering costs \(O(2^m\sum_j c_j)\). A comparison costs \(O(m+p_j)\), and there are at most \(4^m\) ordered pairs per type. Since \(\sum_j c_j=O(L)\) and \(\sum_j p_j=O(L)\), a sufficient deterministic time bound is
\(O\!\left(L^3+2^m(m^2+L)+4^m(\tau m+L)\right)\).
This algorithm uses the supplied support directly; it does not enumerate other possible types.
⟨structured verdict parsed — rendered above⟩
The prover resolves the task correctly. The direct reduction proves \(\mathrm{NP}\)-hardness while respecting the satisfiability promise. The quantified argument and the cited single-type theorem also justify the stronger claim of \(\Sigma_2^p\)-completeness. I found no mathematical gaps requiring repair.
The complete-extension test is correct. The set \(D(E)\) consists exactly of arguments defended by \(E\). Thus \(E\cap f(E)=\varnothing\) establishes conflict-freeness, and \(E=D(E)\) establishes that \(E\) contains exactly its defended arguments. Together these characterize Dung complete extensions.
The claimed \(O(m^2)\) check using an attack matrix is valid: computing \(f(E)\) and checking whether every attacker of each argument belongs to \(f(E)\) each require at most a quadratic scan. For a complete extension, the resulting accepted, defeated, and undecided sets agree with the task’s assignment.
Constraint evaluation is polynomial because every connective has a fixed truth table and the formulas are explicitly represented. Scanning the listed preference relation also correctly decides the comparison: each listed pair is checked against the two specified set differences. Testing both directions determines strict domination. The explicit convention that identical extensions never strictly dominate handles the restriction to distinct extensions.
Finding: Correct.
The common denominator \(H\) is positive and divisible by every \(b_j\) and by \(d\). Therefore multiplying the threshold inequality by \(H\) gives precisely the displayed integer comparison.
The size estimate is sound. The bit length of \(H\) is bounded by the sum of the denominator bit lengths, up to a constant. Since the valid input satisfies \(0<\mu_j\le1\) and \(0<q\le1\), the integers \(W_j\) and \(Q\) are at most \(H\). Intermediate sums also have polynomial bit length.
The stated \(O(L^3)\) bound is sufficient for the product, exact divisions, multiplications, and additions using ordinary integer arithmetic. The explicitly listed support ensures that the number of these operations is bounded by the input length.
Finding: Correct; no approximation or numerical precision assumption is used.
The existential witness has polynomial length: it records the selected indices and at most one \(m\)-bit extension per type. The universally quantified pair \((j,F)\) also has polynomial length.
Conditions 1 and 2 are polynomial-time checks independent of the universal choice. Condition 3 checks that no feasible challenger strictly dominates any selected witness. Invalid indices and unselected indices are explicitly handled. The identical-extension case is covered by the convention established in Section 1.
Both directions of the equivalence are valid:
No assertion that every feasible set has an undominated member is needed. Empty feasible or best-extension sets cannot supply a selected witness, exactly as required.
Finding: Correct, including when \(\tau\) varies with the input.
The construction meets all input requirements. It uses one type, a valid empty strict partial order, positive mass \(1\), and permitted threshold \(1\). Every constraint has an allowed form.
The promise verification is valid. The assignment setting \(g\), all \(x_i\), and all \(y_i\) to \(f\) satisfies every constraint independently of the Boolean satisfiability of \(\phi\). The promise requires an arbitrary three-valued assignment; it does not require this assignment to arise from a complete extension.
The complete-extension characterization is also correct:
Under the specified semantics, \(x_i\vee\neg x_i\) takes value \(u\) when \(x_i=u\), and value \(t\) when \(x_i=f\) or \(x_i=t\). Thus the first group of constraints removes exactly the undecided local choices.
For the surviving extensions, every variable is Boolean-valued and \(g=t\). Hence the last constraint is satisfied exactly when the corresponding Boolean assignment satisfies \(\phi\).
With the empty preference relation, neither direction of strict domination holds between distinct feasible extensions. Therefore all feasible extensions are best, and every one contains \(g\). The final equivalence with Boolean satisfiability follows.
The construction has polynomial size and respects the promise on both satisfiable and unsatisfiable source instances.
Finding: Correct. This section independently settles the task’s requested hardness alternative.
The citation is accurate. Theorem 1 states \(\Sigma_2^p\)-completeness of credulous acceptance for ePAFs under complete semantics. Definition 7 requires a strict partial order on argument–truth-value pairs, and Definition 9 supplies the same KTV comparison. The source’s accepted set is its defended set, which equals \(E\) under complete semantics. [Alfano et al., Definitions 7–9 and Theorem 1](https://www.ijcai.org/proceedings/2023/0345.pdf)
Consequently, adding an empty constraint set, mass \(1\), and threshold \(1\) preserves the source decision problem and satisfies every additional promise here. This is a valid polynomial-time many-one reduction.
Finding: Correct. Together with Section 2, it establishes \(\Sigma_2^p\)-completeness.
The exhaustive algorithm correctly filters complete extensions, applies constraints before preferences, checks every possible strict dominator, and performs the final exact threshold comparison.
There are at most \(2^m\) candidate extensions and \(4^m\) ordered pairs per type. Summing the stated filtering and comparison costs gives the claimed sufficient bound:
\(O\!\left(L^3+2^m(m^2+L)+4^m(\tau m+L)\right)\).
The bound uses the listed support rather than enumerating possible types. It therefore addresses the requested parameters.
Finally, \(\mathrm{NP}\)-hardness implies that a polynomial-time algorithm would yield \(\mathrm{P}=\mathrm{NP}\). The prover correctly states this conditional consequence without claiming an unconditional separation.
Required clarification or repair: None.
⟨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.