d4-conf-ijcai-2011-0152 (d4-conf-ijcai-2011-0152)

Given a common argument set \(X\) and an explicitly listed support \((F_i,\mu_i)_{i=1}^{\tau}\) of frameworks with \(\sum_i\mu_i=1\), output the exact rational vector \(p\) where \(p(a)=\sum_{i=1}^{\tau}\mu_i\,\mathbf{1}[a\in I_{\mathrm{sst}}(F_i)]\) for every \(a\in X\).

Let \(X\) be a finite argument set, \(m=|X|\). A type is a Dung argumentation framework \(F=(X,A)\), with explicitly listed attacks \(A\subseteq X\times X\); self-attacks are allowed.
Use standard Dung admissibility and semi-stable semantics, and write \(\mathcal E_{\mathrm{sst}}(F)\) for the semi-stable extensions. Define \(I_{\mathrm{sst}}(F)\), also called the eager extension, as the unique inclusion-maximal admissible set contained in \(\bigcap_{T\in\mathcal E_{\mathrm{sst}}(F)}T\). Empty extensions are allowed.
A society is given by its support: the list \((F_i,\mu_i)_{i=1}^{\tau}\) of distinct types with positive binary rational masses satisfying \(\sum_{i=1}^{\tau}\mu_i=1\). Here \(\tau\) is the support size, not the number of possible frameworks. Let \(L\) be the total input bit length; state running times in \(m,\tau,L\).
The computational problem is to output the exact rational vector \(p\in\mathbb Q^X\) defined by \(p(a)=\sum_{i=1}^{\tau}\mu_i\mathbf 1[a\in I_{\mathrm{sst}}(F_i)]\).

Is this exact vector computation solvable in polynomial time in \(m,\tau,L\), or is it \(\mathrm{NP}\)-hard under polynomial-time Turing reductions?

For a single finite framework, eager-extension membership is \(\Pi_2^{\mathrm P}\)-complete, and construction is \(\mathrm{FP}^{\Sigma_2^{\mathrm P}}_{\parallel}\)-complete under metric reductions. [Source](https://www.ijcai.org/Proceedings/11/Papers/148.pdf)
No result specifically addressing this exact vector problem with explicitly listed rational support was located in the literature search.

Result. The exact vector problem is \(\mathrm{NP}\)-hard under polynomial-time Turing reductions, already for support size \(\tau=1\). Consequently, a polynomial-time algorithm in \(m,\tau,L\) would imply \(\mathrm P=\mathrm{NP}\).

1. The single-framework theorem applies

Define the decision language
\[ M_{\mathrm{eager}} =\{(F,a):a\in I_{\mathrm{sst}}(F)\}. \]
The supplied theorem states that this language is \(\Pi_2^{\mathrm P}\)-complete. The cited paper defines ideal sets relative to semi-stable semantics as precisely the admissible sets contained in every semi-stable extension, and its Theorem 7 and Table 2 establish the stated complexity. Thus its definition agrees with the task’s eager extension. [Dvořák, Dunne, and Woltran, *Parametric Properties of Ideal Semantics*](https://www.ijcai.org/Proceedings/11/Papers/148.pdf).

In particular, the paper’s formulation using membership in some such admissible set is equivalent to membership in the eager extension: in a finite framework, every such set is contained in an inclusion-maximal such set, and that maximal set is unique by the premise.

We use this published completeness theorem as a given result.

2. A one-type society preserves membership exactly

Let \(V\) denote the requested vector-valued function. Given a framework \(F=(X,A)\), construct the society
\[ S_F=((F,1)). \]
This is a valid input: its support consists of one distinct type, and its sole mass is a positive binary rational summing to \(1\). It preserves the explicitly listed attack relation, including any self-attacks.

For every \(a\in X\), the definition of \(V\) gives
\[ V(S_F)(a) =1\cdot\mathbf 1[a\in I_{\mathrm{sst}}(F)]. \]
Hence
\[ a\in I_{\mathrm{sst}}(F) \quad\Longleftrightarrow\quad V(S_F)(a)=1. \]

Constructing \(S_F\) requires only copying the framework and adding a constant-size mass. Its input length is polynomial in the encoding length of \(F\). One call to an exact vector oracle therefore decides eager membership, followed by a polynomial-time inspection of one coordinate.

3. Explicit polynomial-time Turing reduction from satisfiability

To justify the requested \(\mathrm{NP}\)-hardness directly, use
\[ \mathrm{UNSAT}\in\mathrm{coNP}\subseteq\Pi_2^{\mathrm P}. \]
The containment follows by adding an unused existentially quantified string to the universal polynomial-time predicate characterizing a language in \(\mathrm{coNP}\).

By the \(\Pi_2^{\mathrm P}\)-hardness of \(M_{\mathrm{eager}}\), there is a polynomial-time many-one reduction mapping each Boolean formula \(\varphi\) to a valid pair \((F_\varphi,a_\varphi)\) such that
\[ \varphi\in\mathrm{UNSAT} \quad\Longleftrightarrow\quad a_\varphi\in I_{\mathrm{sst}}(F_\varphi). \]
Query the vector oracle on \(S_{F_\varphi}\). Section 2 yields
\[ \varphi\in\mathrm{SAT} \quad\Longleftrightarrow\quad V(S_{F_\varphi})(a_\varphi)=0. \]

This is a deterministic polynomial-time Turing reduction from \(\mathrm{SAT}\) using one oracle call. Since \(\mathrm{SAT}\) is \(\mathrm{NP}\)-complete, the exact vector problem is \(\mathrm{NP}\)-hard under the requested reductions.

The reduction always has \(\tau=1\), while \(m\) and \(L\) are polynomially bounded in the formula’s input length. Thus allowing explicitly listed support does not remove the hardness.

4. Exact rational aggregation has polynomial cost

For completeness, the numerical part introduces no exponential output length. Write each input mass as
\[ \mu_i=\frac{u_i}{d_i}, \]
with positive integers \(u_i,d_i\), and set
\[ D=\prod_{i=1}^{\tau}d_i. \]
The total bit length of the denominators is at most \(L\), so \(D\) has \(O(L)\) bits.

Once the eager-membership indicators \(b_{ia}\in\{0,1\}\) are known, compute
\[ N_a=\sum_{i=1}^{\tau}b_{ia}u_i\frac{D}{d_i}, \qquad p(a)=\frac{N_a}{D}. \]
All summands are nonnegative, and normalization gives
\[ \sum_{i=1}^{\tau}u_i\frac{D}{d_i}=D. \]
Therefore \(0\leq N_a\leq D\), so every coordinate has \(O(L)\) bits. The complete vector has \(O(mL)\) bits.

Using elementary integer arithmetic, constructing \(D\) and the weighted numerators, summing the selected terms, and reducing the fractions takes
\[ O\!\left((m+1)(\tau+1)(L+1)^3\right) \]
bit operations, a deliberately loose polynomial bound.

Moreover, all \(\tau m\) eager-membership questions can be asked nonadaptively. Since membership is in \(\Pi_2^{\mathrm P}\), their complements can be submitted to a \(\Sigma_2^{\mathrm P}\) oracle and the answers negated. Query preparation and postprocessing take time polynomial in \(m,\tau,L\). Thus
\[ V\in\mathrm{FP}^{\Sigma_2^{\mathrm P}}_{\parallel}. \]

The hardness conclusion is unconditional; excluding a polynomial-time algorithm requires the usual assumption \(\mathrm P\ne\mathrm{NP}\).

⟨structured verdict parsed — rendered above⟩

The prover resolves the task correctly. The reduction establishes \(\mathrm{NP}\)-hardness under polynomial-time Turing reductions even when \(\tau=1\). The rational aggregation and oracle upper bound are also valid. No major or minor mathematical issues were found.

1. Applicability of the single-framework theorem

The cited result concerns finite frameworks with an arbitrary attack relation \(A\subseteq X\times X\), so its domain matches the task and permits self-attacks. Definition 2 defines ideal sets relative to a semantics as admissible sets contained in every extension of that semantics, and ideal extensions as inclusion-maximal such sets. The semi-stable instance therefore agrees with the task’s eager extension. Theorem 7 and Table 2 give the claimed \(\Pi_2^{\mathrm P}\)-completeness of acceptance in such an ideal set. [Cited paper](https://www.ijcai.org/Proceedings/11/Papers/148.pdf).

The prover correctly checks the distinction between membership in some qualifying admissible set and membership in the unique maximal qualifying set. Finiteness ensures that every qualifying set is contained in a maximal qualifying set; uniqueness identifies that maximal set with \(I_{\mathrm{sst}}(F)\). Conversely, the eager extension itself is a qualifying admissible set.

The theorem is explicitly supplied by USER_TASK, so using it as a given result is justified. The prover need not reproduce its hardness construction.

Assessment: Correct; the theorem applies to the stated membership language.

2. Reduction to a one-type society

The society \(S_F=((F,1))\) satisfies every input requirement:

• Its support has size \(\tau=1\), so distinctness is automatic.
• Its mass is positive, binary rational, and sums to \(1\).
• Its framework and explicitly listed attacks are preserved.

The displayed identity
\[ V(S_F)(a)=\mathbf 1[a\in I_{\mathrm{sst}}(F)] \]
follows directly from the requested vector definition. Consequently, the coordinate is exactly \(0\) or \(1\), and inspecting it decides eager membership without numerical approximation.

Copying the framework and adding the mass has polynomial cost. Reading the requested coordinate also has polynomial cost: the vector has \(m\) coordinates, each representing a bit-valued rational on these inputs.

Assessment: Correct polynomial-time oracle reduction.

3. Reduction from satisfiability

Each complexity-theoretic step is valid.

First, \(\mathrm{UNSAT}\in\mathrm{coNP}\subseteq\Pi_2^{\mathrm P}\). The stated explanation using an unused existentially quantified string correctly justifies the containment.

Second, the supplied many-one hardness theorem yields a polynomial-time mapping to valid membership instances satisfying
\[ \varphi\in\mathrm{UNSAT} \quad\Longleftrightarrow\quad a_\varphi\in I_{\mathrm{sst}}(F_\varphi). \]

Third, the singleton-society identity makes complementing the answer valid:
\[ \varphi\in\mathrm{SAT} \quad\Longleftrightarrow\quad V(S_{F_\varphi})(a_\varphi)=0. \]

Negating an oracle answer is permitted in a deterministic polynomial-time Turing reduction. Thus one vector-oracle call decides satisfiability. Since \(\mathrm{SAT}\) is \(\mathrm{NP}\)-complete, the claimed \(\mathrm{NP}\)-hardness follows.

The reduction produces polynomial-size frameworks and societies, so \(m\) and \(L\) are polynomially bounded in the formula length while \(\tau=1\). Hence a running time polynomial in \(m,\tau,L\) would yield a polynomial-time satisfiability algorithm.

Assessment: Correct. The conclusion that such an algorithm would imply \(\mathrm P=\mathrm{NP}\) follows.

4. Rational aggregation and output length

The arithmetic claims check out.

For \(D=\prod_i d_i\), its binary length is bounded by the sum of the denominator lengths, up to a constant. Thus \(D\) has \(O(L)\) bits.

Every quotient \(D/d_i\) is an integer. Normalization gives exactly
\[ \sum_i u_i(D/d_i)=D. \]
Because all terms are nonnegative and each indicator selects or omits a term, \(0\leq N_a\leq D\). Both numerator and denominator therefore have \(O(L)\) bits, and reducing a fraction cannot increase these lengths. The vector-size bound \(O(mL)\) is valid.

The loose bound
\[ O\bigl((m+1)(\tau+1)(L+1)^3\bigr) \]
covers the stated integer products, exact divisions, additions, and fraction reductions using elementary arithmetic. It is explicitly conditional on having the membership indicators; the prover does not mistake it for a polynomial-time solution of the semantic computation.

Assessment: Correct.

5. Nonadaptive oracle upper bound and edge cases

All \(\tau m\) membership queries depend only on the input. Complementing the \(\Pi_2^{\mathrm P}\) membership language gives a \(\Sigma_2^{\mathrm P}\) language, so nonadaptive queries followed by negation and polynomial-time aggregation establish
\[ V\in\mathrm{FP}^{\Sigma_2^{\mathrm P}}_{\parallel}. \]

Empty eager extensions simply give zero indicators. Zero numerators cause no difficulty in fraction reduction. If \(X\) is empty, the output is the empty vector and no membership queries are needed. These cases do not invalidate any claim.

Assessment: Correct.

No additional clarification or repair is needed. The output settles the requested hardness classification; its exclusion of a polynomial-time algorithm is appropriately conditional on \(\mathrm P\ne\mathrm{NP}\).

⟨structured verdict parsed — rendered above⟩