Answer: The exact optimization is polynomial-time solvable, and the budget decision version belongs to \(\mathrm{P}\). It is not NP-hard unless \(\mathrm{P}=\mathrm{NP}\).
Proposition 1(6) — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateLet ⟨A, R⟩be an argumentation framework. 1. There is at least one preferred extension, always a unique grounded extension, while there may be zero, one or many stable extensions. 2. Each admissible set is included in a preferred extension. 3. Each stable extension is a preferred extension, the converse is false. 4.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a rational distribution \(\mu\) over types \(t\), where each type specifies a finite framework \(G_t\), a claim \(q_t\), interactions \(I_t\) for a proposed argument \(z\), and cost \(c_t\), choose mass \(x_t\in[0,\mu_t]\) to receive \(z\) with interactions \(I_t\). Let \(b_t\) and \(g_t\) indicate whether \(q_t\) is in the grounded extension before and after addition. What minimum \(\sum_t c_tx_t\) achieves accepted mass \(\sum_t((\mu_t-x_t)b_t+x_tg_t)\ge\theta\), or is the target infeasible?
A society is given by its support: a list of \(\tau\) types with positive binary-rational masses \(\mu_t\), with \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types.
Each type specifies an explicitly represented finite Dung argumentation framework \(G_t=(A_t,R_t)\), with \(A_t\ne\varnothing\), a designated argument \(q_t\in A_t\), and a nonnegative binary-rational cost \(c_t\) per unit mass receiving the intervention.
The proposed argument \(z\) is absent from every \(A_t\). Its prescribed interactions satisfy \(\varnothing\ne I_t\subseteq(A_t\times\{z\})\cup(\{z\}\times A_t)\); receiving it replaces \(G_t\) by \(G'_t=(A_t\cup\{z\},R_t\cup I_t)\), without changing existing attacks.
Let \(b_t\) and \(g_t\) be the indicators that \(q_t\) belongs to the grounded extension of \(G_t\) and \(G'_t\), respectively. Interventions affect recipients independently.
Given a binary-rational threshold \(\theta\in[0,1]\), choose real masses \(0\le x_t\le\mu_t\) to minimize \(\sum_t c_tx_t\), subject to \(\sum_t((\mu_t-x_t)b_t+x_tg_t)\ge\theta\), or report infeasibility. The budget decision version additionally receives a nonnegative binary-rational \(B\) and requires \(\sum_t c_tx_t\le B\).
Let \(m=\max_t|A_t|\) and let \(L\) be the total binary input length, including the explicit frameworks and all rational data; state running times in \(m,\tau,L\).
Is computing this exact minimum cost, or reporting infeasibility, polynomial-time solvable, or is its budget decision version NP-hard?
For a finite argumentation framework, the grounded extension is computable by iterating the characteristic function from the empty set; this gives a polynomial-time algorithm. This result concerns extension computation, not the society-level intervention optimization.
The exact minimum cost, or infeasibility, is computable in polynomial time. The budget decision version belongs to \(\mathrm{P}\), and therefore is not NP-hard unless \(\mathrm{P}=\mathrm{NP}\).
The society-level optimization reduces to fractional knapsack after computing the grounded acceptance indicators. The fact that intervention masses may be arbitrary real numbers is essential to this reduction.
For a framework \(G=(A,R)\), define its characteristic function by
\[
F_G(S)=\{a\in A:\text{ for every }u\text{ with }(u,a)\in R,\text{ some }v\in S\text{ satisfies }(v,u)\in R\}.
\]
This function is monotone: if \(S\subseteq T\), every argument defended by \(S\) is also defended by \(T\).
Starting with \(S_0=\varnothing\), set \(S_{j+1}=F_G(S_j)\). The sequence is increasing. Indeed, \(S_0\subseteq S_1\), and monotonicity propagates each inclusion to the next. Every strict inclusion adds an argument, so stabilization occurs after at most \(|A|+1\) evaluations. The stabilized set is the grounded extension, by the characterization given in the question.
For completeness, each evaluation takes \(O(|A|+|R|)\) graph operations:
Thus grounded extension computation takes \(O(|A|(|A|+|R|))\) graph operations.
For each type, compute the grounded extensions of both \(G_t\) and \(G'_t\), obtaining \(b_t,g_t\in\{0,1\}\). Since \(G'_t\) has at most \(m+1\) arguments and at most \((m+1)^2\) attacks, computing all these indicators takes \(O(\tau(m+1)^3)\) graph operations.
Define the baseline acceptance mass \(a=\sum_{t=1}^{\tau}\mu_t b_t\) and the acceptance change \(\delta_t=g_t-b_t\in\{-1,0,1\}\). For an allocation \(x\), its resulting acceptance mass is
\[
a+\sum_{t=1}^{\tau}\delta_t x_t.
\]
Let \(P=\{t:\delta_t=1\}\), the set of beneficial types.
Given any feasible allocation, replace \(x_t\) by zero whenever \(t\notin P\). This operation preserves the box constraints. It does not decrease acceptance, because each removed term \(\delta_t x_t\) was nonpositive. It does not increase cost, because \(c_t x_t\) was nonnegative.
Consequently, whenever a feasible allocation exists, an optimal allocation exists that intervenes only on types in \(P\).
If \(a\ge\theta\), the zero allocation is feasible and has minimum cost zero. Henceforth suppose \(a<\theta\), and define the positive deficit \(D=\theta-a\). The remaining optimization is
\[
\text{minimize }\sum_{t\in P}c_t x_t
\quad\text{subject to}\quad
0\le x_t\le\mu_t,\qquad \sum_{t\in P}x_t\ge D.
\]
Every unit of mass allocated to a beneficial type contributes exactly one unit toward the deficit.
The instance is feasible if and only if
\[
D\le\sum_{t\in P}\mu_t.
\]
To prove necessity, any allocation satisfies
\[
a+\sum_t\delta_t x_t
\le a+\sum_{t\in P}x_t
\le a+\sum_{t\in P}\mu_t.
\]
Thus a larger threshold cannot be attained.
For sufficiency, intervene on the entire mass of every beneficial type and on no other types. Its acceptance mass is \(a+\sum_{t\in P}\mu_t\), which meets the threshold under the stated condition.
This also handles \(P=\varnothing\): a positive deficit then makes the instance infeasible.
Suppose the positive deficit is feasible. Relabel the beneficial types as \(1,\ldots,p\), in an order satisfying \(c_1\le\cdots\le c_p\). Break ties arbitrarily.
Define \(S_0=0\) and \(S_j=\sum_{i=1}^j\mu_i\). Let \(k\) be the smallest index with \(S_k\ge D\). Such an index exists by feasibility, and \(S_{k-1}<D\).
Choose
\[
x_i^*=
\begin{cases}
\mu_i,&i<k,\\
D-S_{k-1},&i=k,\\
0,&i>k.
\end{cases}
\]
Set all allocations outside \(P\) to zero. Since \(0<D-S_{k-1}\le\mu_k\), this allocation respects every mass bound and allocates exactly \(D\) beneficial mass.
Its cost is
\[
C^*=\sum_{i<k}c_i\mu_i+c_k(D-S_{k-1}).
\]
To prove optimality, let \(y\) be any feasible allocation supported on \(P\), and write \(\lambda=c_k\). Because \(\sum_i x_i^*=D\),
\[
\sum_i c_i y_i-C^*
=
\lambda\left(\sum_i y_i-D\right)
+\sum_i(c_i-\lambda)(y_i-x_i^*).
\]
Every contribution on the right is nonnegative:
Therefore \(\sum_i c_i y_i\ge C^*\). Section 2 transforms every feasible allocation into one supported on \(P\) with no greater cost, so this proves global optimality. Zero costs and tied costs require no additional assumptions.
The algorithm performs:
Exact rational arithmetic has polynomial bit complexity. To verify this explicitly, let \(Q\) be the product of all denominators appearing in the rational input, using the usual binary numerator-and-denominator encoding. Its bit length is \(O(L)\), because the sum of the input denominators’ bit lengths is at most \(L\).
Every input rational can be written over denominator \(Q\) with an \(O(L)\)-bit numerator. The baseline, deficit, cumulative masses, and greedy allocation also have denominator \(Q\) and \(O(L)\)-bit numerators. The cost can be computed over denominator \(Q^2\), still with an \(O(L)\)-bit numerator: the total intervened mass is at most one, and every input cost has magnitude at most \(2^{O(L)}\).
Thus all arithmetic and comparison operations use integers of \(O(L)\) bits. With schoolbook arithmetic, a conservative overall bit-operation bound is
\[
O\!\left(
\bigl[\tau(m+1)^3+\tau\log(\tau+1)+1\bigr]L^2
\right).
\]
The output allocation and minimum cost have polynomial binary length.
For the budget decision version, reject infeasible instances; otherwise accept exactly when \(C^*\le B\), using an exact rational comparison. This adds only polynomial time.
⟨structured verdict parsed — rendered above⟩
The prover resolves the task correctly. The exact minimum cost and an optimal allocation are computable in polynomial time, and the budget decision version belongs to \(\mathrm{P}\). No major or minor mathematical issues were found.
The argument addresses the society-level optimization explicitly; it does not infer its tractability merely from polynomial-time grounded-extension computation.
The stated characteristic function correctly expresses defense: an argument belongs to \(F_G(S)\) precisely when every attacker is attacked by some member of \(S\). Arguments with no attackers satisfy this condition vacuously.
Monotonicity follows directly from the definition. The inclusions \(S_0\subseteq S_1\) and, inductively, \(S_j\subseteq S_{j+1}\) are justified. On a framework with \(n\) arguments, at most \(n\) strict inclusions can occur, and one further evaluation detects stabilization. Thus the bound of \(n+1\) evaluations is correct.
The identification of the stabilized set with the grounded extension uses exactly the characterization supplied in the task, with its finite-framework hypothesis satisfied.
The proposed evaluation procedure is also correct. Marking arguments attacked by \(S_j\), then marking targets having an unmarked attacker, identifies precisely the arguments failing the defense condition. With explicit attack lists, each evaluation uses \(O(n+|R|)\) graph operations. The resulting \(O(n(n+|R|))\) bound is valid because \(n\ge1\).
Both original and intervened frameworks meet these conditions. Their sizes are bounded by \(m+1\) arguments and \((m+1)^2\) attacks, so the total \(O(\tau(m+1)^3)\) graph-operation bound is justified.
Expanding the task’s acceptance constraint gives exactly \(a+\sum_t\delta_t x_t\), where \(a=\sum_t\mu_t b_t\) and \(\delta_t=g_t-b_t\).
Since both indicators are binary, \(\delta_t\in\{-1,0,1\}\). Setting \(x_t=0\) for every type with \(\delta_t\le0\) preserves the box constraints, weakly increases acceptance, and weakly decreases cost. Each conclusion uses an explicit task hypothesis: \(x_t\ge0\) and \(c_t\ge0\).
Hence restricting optimization to beneficial types preserves feasibility and the minimum cost. Existence of a minimum is also valid: whenever feasible, the feasible region is a closed subset of the compact mass box, and the objective is continuous. The write-up’s use of an optimal allocation therefore introduces no existence gap.
If \(a\ge\theta\), the zero allocation is feasible and optimal because every objective term is nonnegative. This correctly includes equality and \(\theta=0\).
After the baseline case is removed, \(D=\theta-a>0\), and the reduced constraint is exactly \(\sum_{t\in P}x_t\ge D\).
The necessity argument correctly bounds every allocation’s acceptance by \(a+\sum_{t\in P}\mu_t\), including allocations involving harmful types.
The sufficiency argument provides a valid allocation whenever \(D\le\sum_{t\in P}\mu_t\): intervene on every beneficial type’s entire mass. Thus the criterion is necessary and sufficient.
The empty-set case is handled explicitly. When \(P=\varnothing\) and \(D>0\), infeasibility follows immediately. Equality in the feasibility criterion is also covered.
On a feasible positive-deficit instance, \(P\ne\varnothing\). Sorting its types by nondecreasing cost is well-defined, including ties.
The smallest index \(k\) with \(S_k\ge D\) exists by feasibility. Minimality gives \(S_{k-1}<D\), and consequently \(0<D-S_{k-1}\le\mu_k\). These inequalities verify the partially allocated type’s mass bounds.
The proposed allocation has total beneficial mass exactly \(D\), so it meets the threshold. Its stated cost formula follows directly from its coordinates.
Real-valued intervention masses permit this partial allocation. All coordinates produced by the algorithm are nevertheless rational.
The identity
\(\sum_i c_i y_i-C^*=\lambda(\sum_i y_i-D)+\sum_i(c_i-\lambda)(y_i-x_i^*)\)
is algebraically correct: expanding its right-hand side leaves \(\sum_i c_i(y_i-x_i^*)\), using \(\sum_i x_i^*=D\).
Every claimed sign is justified:
Therefore every feasible allocation supported on \(P\) costs at least \(C^*\). Applying the earlier removal operation to an arbitrary feasible allocation extends this bound to the original problem.
The proof correctly accommodates zero costs, tied costs, exact exhaustion of a cumulative mass, and allocations exceeding the required deficit.
Under the stated binary numerator-and-denominator representation, the product \(Q\) of input denominators has \(O(L)\) bits. Every input rational can be converted to denominator \(Q\) with an \(O(L)\)-bit numerator.
The baseline, cumulative masses, deficit, and allocation coordinates have denominator \(Q\). Their magnitudes are bounded by one in the branches where they are used, so their numerators have \(O(L)\) bits.
Each cost product has denominator \(Q^2\). The total cost is at most the largest input cost because total intervened mass is at most one. Since input costs have magnitude at most \(2^{O(L)}\), the final cost numerator also has \(O(L)\) bits. Thus neither the allocation nor the objective requires exponentially many output bits.
Computing the common denominator and converting input rationals requires only polynomial work and fits within the stated conservative bound. Schoolbook arithmetic on the resulting integers costs \(O(L^2)\) per operation or comparison.
The overall bound
\(O((\tau(m+1)^3+\tau\log(\tau+1)+1)L^2)\)
is consequently valid. It accounts for grounded-extension computation, rational processing, sorting, and exact output computation.
Rejecting infeasible instances and otherwise comparing the exact minimum with \(B\) solves the budget decision problem. Nonnegative \(B\), including \(B=0\), poses no additional case.
The conclusion that this decision problem is not NP-hard unless \(\mathrm{P}=\mathrm{NP}\) follows under the usual polynomial-time reduction convention.
None. The hypotheses, feasibility cases, optimality argument, and bit-complexity analysis are sufficient to verify the claimed result.
⟨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.