Answer: \(\Pi_2^p\)-complete under polynomial-time many-one reductions, hence \(\mathrm{NP}\)-hard, already for \(\tau=1\) and mass \(1\).
Theorem 3 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateV erσα and V erσ∗ α are: • in P for σα = coe; • coNP-complete for σα ∈{cok, std, ste, stk, prd}; and • Πp 2-complete for σα ∈{pre, prk, ssd, sse, ssk}. Thus, the complexity of the verification problem for CPAF does not depend on the flat or closed interpretation and coincides with that of PAF where only unconditional preferences are considered.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite argumentation framework \(\Lambda=(A,\Omega)\), a support \(T\) of \(\tau\) well-formed conditional-preference bases \(\Gamma_t\) with positive binary-rational masses \(\mu_t\) summing to \(1\), and a proposed set \(S\), decide whether \(S\) is a preferred extension of \(\Lambda\) that is unbeaten by weighted majority. For each pair of preferred extensions \(E,F\), each type compares them by the paper’s flat KTV criterion; define \(w_\mu(E,F)=\sum_{t:E\succ_{k,t}F}\mu_t\), with ties and incomparisons abstaining, and say \(E\succ_\mu F\) iff \(w_\mu(E,F)>w_\mu(F,E)\). The question is whether there is no \(F\in pr(\Lambda)\) with \(F\succ_\mu S\).
Given a finite argumentation framework \(\Lambda=(A,\Omega)\), put \(m=|A|\), and let \(\operatorname{pr}(\Lambda)\) denote its Dung preferred extensions. The proposed set is \(S\subseteq A\).
A society is given by its support: a list \(T\) of \(\tau\) types with positive binary-rational masses \(\mu_t\), with \(\sum_{t\in T}\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types. Each type explicitly supplies a finite conditional-preference base \(\Gamma_t\); let \(L\) be the total input bit length. State running times in \(m,\tau,L\).
A rule is \(a>b\leftarrow\bigwedge_{p\in P}p\wedge\bigwedge_{n\in N}\neg n\), where all arguments appearing in the rule are distinct and belong to \(A\); either body set may be empty. Each \(\Gamma_t\) is well-formed: some \(\phi_t:A\to\mathbb N\) assigns equal values to the two head arguments of every rule and a different value to every argument in its body. Empty bases are allowed.
For an extension \(E\), define \(E^+=\{b\in A:\exists a\in E\;(a,b)\in\Omega\}\). A rule body is satisfied by \(E\) precisely when \(P\subseteq E\) and \(N\subseteq E^+\).
For distinct preferred extensions \(E,F\), define \(E\succeq_{k,t}F\) iff no rule \(a>b\leftarrow\mathrm{body}\) in \(\Gamma_t\) has \(a\in F\setminus E\), \(b\in E\setminus F\), and its body satisfied by both extensions. Define \(E\succ_{k,t}F\) iff \(E\succeq_{k,t}F\) and \(F\not\succeq_{k,t}E\); no transitive closure of rules is taken.
Put \(w_\mu(E,F)=\sum_{t:E\succ_{k,t}F}\mu_t\) and \(E\succ_\mu F\) iff \(w_\mu(E,F)>w_\mu(F,E)\). Ties and incomparisons abstain; identical extensions never strictly beat themselves.
The decision problem asks whether \(S\in\operatorname{pr}(\Lambda)\) and there is no \(F\in\operatorname{pr}(\Lambda)\) with \(F\succ_\mu S\).
Is this decision problem solvable in polynomial time, or is it \(\mathrm{NP}\)-hard?
For a single conditional-preference base, verification of an unbeaten preferred extension under flat KTV is \(\Pi_2^p\)-complete; comparison of two extensions is polynomial-time ([source](https://ceur-ws.org/Vol-3464/short1.pdf)).
No result for exactly the support-encoded rational-mass majority problem was located in the literature search.
The decision problem is \(\Pi_2^p\)-complete under polynomial-time many-one reductions, already when \(\tau=1\) and the unique mass is \(1\). Consequently, it is \(\mathrm{NP}\)-hard and cannot be solved in polynomial time unless \(\mathrm{P}=\mathrm{NP}\).
The hardness proof uses the single-base completeness theorem supplied in the question. The upper bound is proved below directly for the support-encoded rational-mass problem.
For a type \(t\) and distinct sets \(E,F\), define \(H_t(E,F)\) to mean that some rule in \(\Gamma_t\) has its preferred head argument in \(E\setminus F\), its other head argument in \(F\setminus E\), and its body satisfied by both sets.
The definitions give
\(E\succeq_{k,t}F\iff\neg H_t(F,E)\),
and therefore
\(E\succ_{k,t}F\iff H_t(E,F)\wedge\neg H_t(F,E)\).
Compute \(E^+\) and \(F^+\) by scanning the attack relation, taking \(O(m^2)\) time. Then scan every explicitly supplied rule, checking its head memberships and all body literals. The total rule-scanning time is \(O(L)\).
The masses can also be compared exactly in polynomial time. Write \(\mu_t=p_t/q_t\), and set \(D=\prod_{t\in T}q_t\). Its binary length is \(O(L)\). Define the integer weight \(c_t=p_t(D/q_t)\). Then
\(w_\mu(E,F)>w_\mu(F,E)\iff \sum_{t:E\succ_{k,t}F}c_t> \sum_{t:F\succ_{k,t}E}c_t\).
Using elementary integer arithmetic, all \(c_t\) can be computed in \(O(\tau L^2)\) time. Thereafter, a comparison takes \(O(m^2+L+\tau L)\) time. Thus a conservative bound including preprocessing is \(O(m^2+L+\tau L^2)\).
For the upper-bound argument, extend this polynomial comparison procedure to arbitrary subsets, and define \(B(E,F)\) to be its strict-majority outcome, with \(B(E,E)\) false. On distinct preferred extensions, \(B\) agrees exactly with \(\succ_\mu\).
A set \(X\subseteq A\) is admissible if it is conflict-free and defends each of its members: for every \(x\in X\) and every attacker \(y\) of \(x\), some \(z\in X\) attacks \(y\). Write \(\operatorname{Adm}(X)\) for this predicate. It is decidable in \(O(m^2)\) time by computing \(X^+\) and scanning the attacks.
By definition, preferred extensions are precisely the inclusion-maximal admissible sets. Hence
\(X\in\operatorname{pr}(\Lambda)\iff \operatorname{Adm}(X)\wedge \forall Y\subseteq A\, \bigl(X\subsetneq Y\Rightarrow\neg\operatorname{Adm}(Y)\bigr)\).
For subsets \(U,F,V\subseteq A\), let \(R(U,F,V)\) be the conjunction of:
The required decision condition is equivalent to
\(\forall U\subseteq A\;\forall F\subseteq A\;\exists V\subseteq A\;R(U,F,V)\).
To verify this equivalence, suppose first that \(S\) is preferred and unbeaten. Conditions 1 and 2 hold for every \(U\). For each \(F\), condition 3 holds immediately if \(F\) is inadmissible or does not beat \(S\). Otherwise, \(F\) must be admissible but nonpreferred, so it has an admissible proper superset \(V\).
Conversely, suppose the quantified formula holds. Conditions 1 and 2 imply that \(S\) is preferred. If a preferred extension \(F\) beat \(S\), the first two disjuncts of condition 3 would be false. The last disjunct would require an admissible proper superset of \(F\), contradicting its preferredness.
Each quantified set uses \(m\) bits, and \(R\) is computable in polynomial time, with the conservative bound \(O(m^2+L+\tau L^2)\). The universal sets can be combined into one block, so this is a \(\forall\exists\) characterization with a polynomial-time predicate. The problem therefore belongs to \(\Pi_2^p\).
We use the supplied theorem that verifying an unbeaten preferred extension for one well-formed conditional-preference base under flat KTV is \(\Pi_2^p\)-complete. The cited paper’s body satisfaction, well-formedness, flat KTV comparison, and best-extension definitions coincide with those in the question; Table 1 lists \(\Pi_2^p\)-completeness for preferred-extension verification under KTV. [Alfano et al., definitions and Table 1](https://ceur-ws.org/Vol-3464/short1.pdf).
Given a single-base instance \((\Lambda,\Gamma,S)\), construct the society
\(T=\{t\},\qquad\Gamma_t=\Gamma,\qquad\mu_t=1\).
This construction preserves the framework, proposed set, rules, and their well-formedness witness. The mass is a positive binary rational, its encoding has constant length, and the masses sum to \(1\). The reduction takes linear time in the source input length.
Strict KTV preference is asymmetric: \(E\succ_{k,t}F\) requires both \(E\succeq_{k,t}F\) and \(F\not\succeq_{k,t}E\), which excludes \(F\succ_{k,t}E\). Consequently, in this singleton society,
\(E\succ_\mu F\iff E\succ_{k,t}F\).
Indeed, a strict KTV preference produces weights \(1\) and \(0\); if neither direction is strict, both weights are \(0\). Thus the constructed instance accepts exactly when the original single-base instance accepts. This proves \(\Pi_2^p\)-hardness.
Finally, \(\mathrm{NP}\subseteq\Pi_2^p\): an existential polynomial-time certificate characterization can be preceded by a universal quantifier whose value the verifier ignores. Therefore \(\Pi_2^p\)-hardness under polynomial-time many-one reductions implies \(\mathrm{NP}\)-hardness.
An exhaustive algorithm provides the bound
\(O\bigl(\tau L^2+2^m(m^2+L+\tau L)\bigr)\).
To obtain it, first compute admissibility for all \(2^m\) subsets in \(O(2^m m^2)\) time. Let \(C(X)\) indicate whether some admissible superset of \(X\), possibly \(X\) itself, exists. Compute it in decreasing order of set size using
\(C(X)=\operatorname{Adm}(X)\vee \bigvee_{a\in A\setminus X}C(X\cup\{a\})\).
This takes \(O(m2^m)\) time. A set \(X\) is preferred exactly when it is admissible and every \(C(X\cup\{a\})\) is false. Finally, check \(S\)’s preferredness and compare every preferred extension against \(S\), using the preprocessed integer masses.
The lower and upper complexity bounds establish the claimed completeness.
⟨structured verdict parsed — rendered above⟩
The output resolves the assigned problem. The comparison procedure, quantified upper bound, singleton-support reduction, and exhaustive algorithm are correct. The cited theorem applies to the definitions given in the task. No major or minor issues were found.
The definition of \(H_t(E,F)\) correctly records a rule favoring an argument in \(E\setminus F\) over one in \(F\setminus E\), with its body satisfied by both sets. Consequently, both displayed equivalences are correct:
\[ E\succeq_{k,t}F\iff\neg H_t(F,E), \qquad E\succ_{k,t}F\iff H_t(E,F)\wedge\neg H_t(F,E). \]
The direction of the arguments in these expressions is important and is handled correctly.
Computing the attacked sets requires at most \(O(m^2)\) time. Scanning the explicitly encoded rules checks exactly the required head memberships, positive-body memberships, and negative-body memberships in the attacked sets. Empty bodies present no difficulty: their satisfaction conditions are vacuous.
The exact rational comparison is valid. The product \(D\) is a positive common denominator whose binary length is bounded by the total encoded denominator length, hence \(O(L)\). Each \(c_t=p_t(D/q_t)\) is an integer, and multiplying both weight sums by \(D\) preserves their strict inequality. The stated \(O(\tau L^2)\) arithmetic preprocessing bound is conservative and polynomial.
The procedure correctly treats ties and incomparisons as abstentions. Explicitly setting \(B(E,E)\) to false also respects the task’s convention for identical extensions.
The admissibility predicate includes both conflict-freeness and defense of every member. Its stated polynomial running time is valid.
The characterization of preferred extensions as inclusion-maximal admissible sets is correct. In particular, maximality is expressed over all proper supersets, rather than merely admissible one-element additions.
The proposed quantified formula has the correct quantifier order:
\[ \forall U\subseteq A\;\forall F\subseteq A\;\exists V\subseteq A\;R(U,F,V). \]
Both directions of its claimed equivalence are justified:
When the first or second disjunct of condition 3 holds, an existential \(V\) remains available because the collection of subsets always contains the empty set. Thus there is no hidden existential-domain issue.
All quantified objects have polynomial length, and the matrix is polynomial-time computable. Combining \(U\) and \(F\) into one universal block therefore establishes membership in \(\Pi_2^p\).
The theorem is stated with the relevant semantics and restrictions. Checking the source confirms that its rule syntax, well-formedness condition, body satisfaction, flat KTV comparison, and definition of best extensions match the task. Its Table 1 reports \(\Pi_2^p\)-completeness for preferred-extension verification under KTV and states that the flat and closed complexity results coincide. [Alfano et al., definitions and Table 1](https://ceur-ws.org/Vol-3464/short1.pdf).
Accordingly, the citation supplies the required source hardness result. The prover does not need to reproduce that theorem’s proof.
The construction preserves the framework, candidate set, and conditional-preference base. Its sole mass is positive, has constant-length binary-rational encoding, and sums to one. Well-formedness is preserved without requiring a witness to be included in the input.
Strict KTV preference is asymmetric by its definition. With one type, a strict preference therefore produces opposing weights \(1\) and \(0\); absence of strict preference in either direction produces weights \(0\) and \(0\). Hence the claimed equivalence
\[ E\succ_\mu F\iff E\succ_{k,t}F \]
holds. Identical extensions cannot create an exception.
The mapping is polynomial-time and preserves acceptance in both directions. It establishes the claimed \(\Pi_2^p\)-hardness already for singleton support.
The subsequent implication to \(\mathrm{NP}\)-hardness is also correct: the stated dummy-universal-quantifier argument establishes \(\mathrm{NP}\subseteq\Pi_2^p\). A polynomial algorithm would consequently imply \(\mathrm{P}=\mathrm{NP}\).
The recurrence for \(C(X)\) correctly detects an admissible superset, including \(X\) itself. Decreasing set-size order ensures that each referenced value has already been computed.
Every proper superset contains some \(X\cup\{a\}\), so the criterion using all such \(C(X\cup\{a\})\) correctly tests maximality. It does not assume that admissibility is preserved when removing arguments.
The admissibility enumeration, recurrence computation, and subsequent comparisons fit the stated bound:
\[ O\bigl(\tau L^2+2^m(m^2+L+\tau L)\bigr). \]
Empty preference bases yield no strict votes, as required. Empty candidate sets and the empty framework are covered by the admissibility and maximality definitions. No additional mathematical clarification is needed.
⟨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.