d4-conf-aaai-2018-0935 (d4-conf-aaai-2018-0935)

Given a finite type set \(T\), rational masses \(\mu_t\) summing to \(1\), initial evaluations \(e_t\in[0,1]\cup\{\ast\}\), a rational symmetric contact kernel \(W_{tu}\), and a rational threshold \(\rho\), decide whether a feasible type-level intervention reaches revenue at least \(\rho\). For an initial voter type choose \(p_t=1\) and \(e_t\le s_t\le1\); for an initial nonvoter choose either \(p_t=s_t=0\) or \(0<p_t\le1\) and \(0<s_t\le p_t\), representing the fraction converted to voters and their aggregate rating mass. Define \(R_t=\frac{\sum_u\mu_uW_{tu}s_u}{\sum_u\mu_uW_{tu}p_u}\), require positive initial voter exposure for every type, let \(C=\sum_t\mu_t c_t\) with \(c_t=s_t-e_t\) for initial voters and \(c_t=s_t\) for initial nonvoters, and let \(U_0\) be the initial population-average personalized rating. Is there an intervention with \(C\le U_0\) and \(\sum_t\mu_tR_t-C-U_0\ge\rho\)?

A society is given by its support: a list \(T\) of \(\tau\) types with positive binary rational masses \(\mu_t\), summing to \(1\); \(\tau\) is the support size, not the number of possible types.
There is one rated object (\(m=1\)). Input consists of initial evaluations \(e_t\in(\mathbb Q\cap[0,1])\cup\{\ast\}\), a symmetric kernel \(W\in\mathbb Q_{\ge0}^{T\times T}\) with \(W_{tt}>0\), and a threshold \(\rho\in\mathbb Q\). Let \(V=\{t:e_t\ne\ast\}\), require \(\varnothing\ne V\subsetneq T\), and require \(\sum_{u\in V}\mu_uW_{tu}>0\) for every \(t\).
Define initial utility per unit population by \(U_0=\sum_{t\in T}\mu_t\frac{\sum_{u\in V}\mu_uW_{tu}e_u}{\sum_{u\in V}\mu_uW_{tu}}\).
An intervention chooses real variables \((p_t,s_t)\): for \(t\in V\), require \(p_t=1\) and \(e_t\le s_t\le1\); otherwise require either \(p_t=s_t=0\), or \(0<p_t\le1\) and \(0<s_t\le p_t\). Here \(p_t\) is the voting fraction and \(s_t\) its aggregate rating mass within type \(t\); unconverted individuals remain nonvoters.
Set \(R_t=\frac{\sum_{u\in T}\mu_uW_{tu}s_u}{\sum_{u\in T}\mu_uW_{tu}p_u}\) and \(C=\sum_{t\in V}\mu_t(s_t-e_t)+\sum_{t\notin V}\mu_ts_t\). Feasibility means \(C\le U_0\); revenue is \(\sum_{t\in T}\mu_tR_t-C-U_0\). The intervention making no changes is allowed.
Is deciding whether a feasible intervention has revenue at least \(\rho\) in \(\mathrm P\), or is it \(\mathrm{NP}\)-hard? State running times in \(m=1\), \(\tau\), and the total binary input length \(L\).
The discrete counterpart, with an explicitly listed undirected customer network including self-connections, unit costs for rating increases, and conversion of nonvoters through positive bribes, is \(\mathrm{NP}\)-complete ([Grandi, Stewart and Turrini, 2018](https://wrap.warwick.ac.uk/95168/13/WRAP-complexity-bribery-network-based-rating-systems-Turrini-2018.pdf)).
No result settling this exact continuous problem was identified in the literature search.

Result

The exact continuous decision problem is $\mathrm{NP}$-hard already for $m=1$, when the support size $\tau$ is variable.

An exact algorithm takes
$$ \tau^{O(\tau)}L^{O(1)} $$
bit operations. Consequently, the problem is polynomial-time solvable for every fixed $\tau$, but a polynomial-time algorithm for variable $\tau$ would imply $\mathrm P=\mathrm{NP}$.

The hardness proof below controls all permitted real interventions, including fractional conversions.

1. A normal-form lemma

Let $N=T\setminus V$.

Lemma. Every feasible intervention can be replaced, without increasing cost or decreasing revenue, by one satisfying $p_u=s_u$ for every $u\in N$.

Proof. Keep all rating masses unchanged and replace each nonvoter’s voting fraction $p_u$ by $s_u$.

If $s_u=0$, the intervention rules already imply $p_u=0$. Otherwise, $0<s_u\leq1$, so the replacement is permitted.

Every rating numerator remains unchanged. Since $W$ is nonnegative and $s_u\leq p_u$, every denominator weakly decreases. It remains positive because the initial voters contribute
$$ d_t=\sum_{v\in V}\mu_vW_{tv}>0. $$
All numerators are nonnegative, so every rating weakly increases. Cost depends only on rating masses and therefore remains unchanged. This proves the lemma.

Thus it suffices to consider variables $s_v\in[e_v,1]$ for initial voters and $x_u=p_u=s_u\in[0,1]$ for initial nonvoters. Conversely, every such point satisfying the budget defines an allowed original intervention.

For $\rho\leq0$, the unchanged intervention answers yes. The reduction below uses $\rho>0$.

2. Construction from CLIQUE

We reduce from the standard $\mathrm{NP}$-complete CLIQUE problem: given a simple undirected graph $G$ and an integer $k$, decide whether $G$ contains $k$ pairwise adjacent vertices.

We may restrict to graphs on $n\geq2$ vertices and $2\leq k\leq n$, since the excluded cases are immediately decidable. Write
$$ M=|E(G)|,\qquad d_i=|\Gamma(i)|, $$
where $\Gamma(i)$ is the neighborhood of vertex $i$.

Define rational parameters
$$ b=\frac1{5n+2k}, \qquad \varepsilon=\frac1{10^8n^8}, \qquad h_i=d_i+\frac43, \qquad H_i=h_i+d_i. $$
In particular,
$$ 0<H_i=2d_i+\frac43\leq2n. $$

Create an anchor type $a$ and, for each graph vertex $i$, two types $v_i,u_i$. Their masses and initial evaluations are
$$ \mu_a=b(n+2k),\qquad e_a=1, $$
$$ \mu_{v_i}=3b,\qquad e_{v_i}=0, \qquad \mu_{u_i}=b,\qquad e_{u_i}=\ast. $$
The masses are positive and sum to
$$ b(n+2k)+4bn=b(5n+2k)=1. $$
The initial voters are exactly $a,v_1,\ldots,v_n$.

Set $W_{aa}=1$ and isolate the anchor from all other types. Within each pair, set
$$ W_{v_iv_i}=\frac{1+\varepsilon h_i}{9b^2}, \qquad W_{v_iu_i}=W_{u_iv_i}=\frac1{3b^2}, \qquad W_{u_iu_i}=\frac1{b^2}. $$
For distinct vertices, set
$$ W_{v_iv_j}= \begin{cases} \displaystyle\frac{\varepsilon}{9b^2},&\{i,j\}\in E(G),\\ 0,&\{i,j\}\notin E(G). \end{cases} $$
All other entries are zero.

This kernel is symmetric, nonnegative, and has positive diagonal. Every type sees an initial voter: the anchor sees itself, $v_i$ sees itself, and $u_i$ sees $v_i$.

Initially, the anchor’s rating is one and every other type’s rating is zero. Hence
$$ U_0=\mu_a=b(n+2k). $$

Finally, define
$$ I=3\binom{k}{2}+k-3M-n, \qquad \rho=b\left[n+\varepsilon\left(I-\frac12\right)\right]. $$

We prove that this society admits a feasible intervention with revenue at least $\rho$ exactly when $G$ has a $k$-clique.

3. Exact revenue formula

By the normal-form lemma, write
$$ z_i=s_{v_i}\in[0,1], \qquad x_i=p_{u_i}=s_{u_i}\in[0,1]. $$
The anchor cannot change because its initial evaluation is one.

The two ratings associated with vertex $i$ are
$$ R_{u_i}=\frac{z_i+x_i}{1+x_i}, $$
$$ R_{v_i} = \frac{(1+\varepsilon h_i)z_i+x_i+ \varepsilon\sum_{j\in\Gamma(i)}z_j} {1+x_i+\varepsilon H_i}. $$
The cost is
$$ C=b\sum_{i=1}^n(3z_i+x_i). $$
Thus feasibility is exactly
$$ \sum_{i=1}^n(3z_i+x_i)\leq n+2k. $$

The anchor’s contribution to utility cancels $U_0$. Revenue is therefore $bG_\varepsilon(z,x)$, where
$$ G_\varepsilon(z,x) = \sum_{i=1}^n \left(3R_{v_i}+R_{u_i}-3z_i-x_i\right). $$

At $\varepsilon=0$, define
$$ g(z,x)=4\frac{z+x}{1+x}-3z-x, \qquad G_0(z,x)=\sum_{i=1}^n g(z_i,x_i). $$

Each individual function $g$ has two equally profitable choices:
$$ g(1,0)=g(0,1)=1. $$
Their normalized costs are respectively $3$ and $1$. The next lemma quantifies the loss incurred away from these choices.

4. Quantitative rounding of fractional choices

For $z,x\in[0,1]$, put $\delta=1-g(z,x)$. Direct calculation gives
$$ \delta = zx+(1-z)\frac{(1-x)^2}{1+x}. $$
Consequently, $\delta\geq0$.

Also, $g$ is affine in $z$, with endpoint values
$$ g(1,x)=1-x, \qquad g(0,x)=\frac{x(3-x)}{1+x}. $$
Both are nonnegative on $[0,1]$, so $0\leq\delta\leq1$.

Round $(z,x)$ as follows:
$$ (\bar z,\bar x)= \begin{cases} (1,0),&x\leq\frac12,\\ (0,1),&x>\frac12. \end{cases} $$

Rounding bound.
$$ |z-\bar z|+|x-\bar x|\leq10\sqrt{\delta}. $$

Proof. If $x\leq1/2$, then
$$ \frac{(1-x)^2}{1+x}\geq\frac16. $$
Hence $1-z\leq6\delta$, and
$$ x=zx+(1-z)x\leq\delta+3\delta=4\delta. $$
The distance to $(1,0)$ is therefore at most $10\delta\leq10\sqrt{\delta}$.

If $x>1/2$, then $\delta\geq z/2$, so $z\leq2\delta$. Moreover,
$$ (1-z)(1-x)^2\leq2\delta, $$
which implies
$$ (1-x)^2 =z(1-x)^2+(1-z)(1-x)^2 \leq z+2\delta \leq4\delta. $$
The distance to $(0,1)$ is at most
$$ z+1-x\leq2\delta+2\sqrt{\delta}\leq4\sqrt{\delta}. $$
This proves the bound.

Apply this rounding separately to every pair. Define
$$ \Delta=n-G_0(z,x)=\sum_{i=1}^n\delta_i, $$
and
$$ \ell=\sum_{i=1}^n \left(|z_i-\bar z_i|+|x_i-\bar x_i|\right). $$
Cauchy–Schwarz gives
$$ \ell\leq10\sum_i\sqrt{\delta_i} \leq10\sqrt{n\Delta}. $$

Let $S$ be the set of vertices rounded to $(1,0)$. The rounded normalized cost is
$$ n+2|S|. $$
Its difference from the original normalized cost has absolute value at most $3\ell$. In particular, a feasible point whose rounding satisfies $3\ell<2$ must have $|S|\leq k$.

5. Uniform bounds on the kernel perturbation

Define
$$ D_i=1+x_i, \qquad r_i=\frac{z_i+x_i}{D_i}, $$
and
$$ K_i=h_i(z_i-r_i)+ \sum_{j\in\Gamma(i)}(z_j-r_i). $$
Because all $z_j,r_i$ belong to $[0,1]$,
$$ |K_i|\leq h_i+d_i=H_i. $$

The exact rating identity is
$$ R_{v_i} = r_i+\frac{\varepsilon K_i}{D_i+\varepsilon H_i}. $$
Define
$$ Q(z,x)=3\sum_{i=1}^n\frac{K_i}{D_i}. $$
Then
$$ G_\varepsilon = G_0+\varepsilon Q+\mathcal R, $$
where
$$ \mathcal R = -3\varepsilon^2 \sum_{i=1}^n \frac{K_iH_i}{D_i(D_i+\varepsilon H_i)}. $$

Since $D_i\geq1$ and $H_i\leq2n$, we obtain the uniform bounds
$$ |G_\varepsilon-G_0| \leq3\varepsilon\sum_iH_i \leq6\varepsilon n^2, $$
$$ |\mathcal R| \leq3\varepsilon^2\sum_iH_i^2 \leq12\varepsilon^2n^3. $$

We also need a Lipschitz bound for $Q$. For two points $(z,x),(z',x')$, write
$$ \ell_i=|z_i-z_i'|+|x_i-x_i'|. $$
The derivatives
$$ \frac{\partial r_i}{\partial z_i}=\frac1{1+x_i}, \qquad \frac{\partial r_i}{\partial x_i} =\frac{1-z_i}{(1+x_i)^2} $$
have absolute value at most one throughout the box. Integrating along the line segment between the two points therefore gives
$$ |r_i-r_i'|\leq\ell_i. $$
It follows that
$$ |K_i-K_i'| \leq2H_i\ell_i+\sum_{j\in\Gamma(i)}\ell_j. $$
Furthermore, $|D_i-D_i'|\leq\ell_i$, and both denominators are at least one. Thus
$$ \left|\frac{K_i}{D_i}-\frac{K_i'}{D_i'}\right| \leq3H_i\ell_i+\sum_{j\in\Gamma(i)}\ell_j. $$
Summing and using $H_i\leq2n$ and $d_i\leq n$ gives
$$ |Q(z,x)-Q(z',x')| \leq21n\sum_i\ell_i. $$

These estimates hold for every real point in the intervention box.

6. The perturbation counts edges at rounded choices

For a subset $S$ of graph vertices, consider the point
$$ (z_i,x_i)= \begin{cases} (1,0),&i\in S,\\ (0,1),&i\notin S. \end{cases} $$
Write $Q(S)$ for $Q$ at this point, and $E(S)$ for the number of graph edges with both endpoints in $S$.

If $i\in S$, then $r_i=1$, $D_i=1$, and
$$ 3\frac{K_i}{D_i}=-3|\Gamma(i)\setminus S|. $$
If $i\notin S$, then $r_i=1/2$, $D_i=2$. Using $h_i=d_i+4/3$, we obtain
$$ 3\frac{K_i}{D_i} = -\frac32|\Gamma(i)\setminus S|-1. $$

An edge crossing from $S$ to its complement is counted once in the first expression. An edge entirely outside $S$ is counted twice in the second expression. Therefore
$$ Q(S) = -3\bigl(M-E(S)\bigr)-(n-|S|), $$
or equivalently,
$$ Q(S)=3E(S)+|S|-3M-n. $$

If $S$ is a $k$-clique, then $Q(S)=I$.

If $G$ has no $k$-clique and $|S|\leq k$, then
$$ Q(S)\leq I-1. $$
Indeed, when $|S|=k$, the missing clique edge gives
$$ E(S)\leq\binom{k}{2}-1, $$
and consequently $Q(S)\leq I-3$. When $|S|=j<k$, use $E(S)\leq\binom j2$ and the fact that
$$ f(j)=3\binom j2+j $$
is strictly increasing on nonnegative integers, with
$$ f(j+1)-f(j)=3j+1\geq1. $$

7. Correctness of the reduction

7.1 A clique produces a feasible intervention above the threshold

Suppose $S$ is a $k$-clique. Choose $(z_i,x_i)=(1,0)$ on $S$ and $(0,1)$ outside it.

Its normalized cost is $n+2k$, so it exactly satisfies the budget. Also,
$$ G_0=n,\qquad Q=I. $$
The remainder bound yields
$$ G_\varepsilon\geq n+\varepsilon I-12\varepsilon^2n^3. $$
Since
$$ 12\varepsilon n^3 =\frac{12}{10^8n^5}<\frac14, $$
we have
$$ G_\varepsilon > n+\varepsilon\left(I-\frac14\right) > n+\varepsilon\left(I-\frac12\right). $$
Multiplying by $b$ proves that its revenue exceeds $\rho$.

7.2 Every intervention above the threshold implies a clique

Suppose $G$ has no $k$-clique, but a feasible intervention has revenue at least $\rho$. Normalize it using Section 1. Its variables then satisfy
$$ G_\varepsilon(z,x) \geq n+\varepsilon\left(I-\frac12\right). $$

Because $M\leq n(n-1)/2$, $n\geq2$, and $k\geq2$,
$$ I-\frac12\geq-3n^2. $$
Hence
$$ G_\varepsilon\geq n-3\varepsilon n^2. $$
Combining this with $G_\varepsilon\leq G_0+6\varepsilon n^2$ gives
$$ \Delta=n-G_0\leq9\varepsilon n^2. $$
The rounding bound therefore gives
$$ \ell\leq10\sqrt{n\Delta} \leq30\sqrt{\varepsilon}\,n^{3/2}. $$

For our choice of $\varepsilon$,
$$ 3\ell \leq\frac{90}{10^4n^{5/2}}<2. $$
Since the original point is feasible,
$$ n+2|S| \leq n+2k+3\ell <n+2k+2. $$
Integrality of $|S|$ implies $|S|\leq k$. Section 6 now gives
$$ Q(S)\leq I-1. $$

Using $G_0\leq n$, the Lipschitz bound, and the remainder bound, we obtain
$$ G_\varepsilon(z,x) \leq n+\varepsilon\left(I-1+21n\ell+12\varepsilon n^3\right). $$
But
$$ 21n\ell+12\varepsilon n^3 \leq 630\sqrt{\varepsilon}\,n^{5/2} +12\varepsilon n^3 $$
$$ = \frac{630}{10^4n^{3/2}} +\frac{12}{10^8n^5} <\frac14. $$
Consequently,
$$ G_\varepsilon(z,x) < n+\varepsilon\left(I-\frac34\right) < n+\varepsilon\left(I-\frac12\right), $$
contradicting the assumed revenue threshold.

This proves both directions, including the exclusion of all fractional witnesses in no-instances.

8. Encoding size and exact running time

8.1 Polynomial size of the hardness reduction

The construction has
$$ m=1,\qquad \tau=2n+1. $$
Every mass, evaluation, kernel entry, and threshold has binary encoding length $O(\log n)$. The explicitly listed kernel has $O(n^2)$ entries, so the resulting total input length satisfies
$$ L=O(n^2\log n). $$
Constructing it takes polynomial time.

The threshold is positive: the estimate $I-1/2\geq-3n^2$ gives
$$ \frac{\rho}{b}\geq n-3\varepsilon n^2>0. $$
Thus the reduction does not use the trivial nonpositive-threshold case.

We have established a polynomial-time many-one reduction from CLIQUE, proving $\mathrm{NP}$-hardness for variable support size.

8.2 General exact algorithm

For an arbitrary valid input, use the normal-form variables from Section 1 and define
$$ D_t(x)= \sum_{v\in V}\mu_vW_{tv} +\sum_{u\in N}\mu_uW_{tu}x_u, $$
$$ A_t(s,x)= \sum_{v\in V}\mu_vW_{tv}s_v +\sum_{u\in N}\mu_uW_{tu}x_u. $$
Every $D_t$ is strictly positive on the intervention box.

Introduce one real variable $r_t$ per type and impose
$$ r_tD_t(x)-A_t(s,x)=0. $$
Together with the intervention bounds, budget inequality, and revenue inequality
$$ \sum_t\mu_tr_t-C(s,x)-U_0\geq\rho, $$
this is an existential polynomial system with:

• $2\tau$ real variables;
• $O(\tau)$ polynomial constraints;
• maximum degree two.

Strict positivity of $D_t$ ensures that its equations force precisely the intended ratings, so feasibility of this system is equivalent to the original decision problem.

The rational number $U_0$ is computable in polynomial bit time. Clearing rational denominators produces integer polynomials with coefficient bit lengths polynomial in $L$.

The singly exponential existential-real decision theorem gives bit complexity $(sd)^{O(q)}B^{O(1)}$ for $q$ variables, $s$ constraints, maximum degree $d$, and integer coefficient bit-length bound $B$. This follows from the single-block specialization and intermediate bit-size bounds of [Basu’s survey, Theorem 2.18](https://www.math.purdue.edu/~sbasu/raag_survey2011_final.pdf). Its hypotheses apply here with $q=2\tau$, $s=O(\tau)$, $d=2$, and $B=L^{O(1)}$.

Therefore the exact running time, for $m=1$, is
$$ \tau^{O(\tau)}L^{O(1)}. $$
The same formulation establishes membership in $\exists\mathbb R$. The proved classification is $\mathrm{NP}$-hardness, with polynomial-time solvability when $\tau$ is fixed.

⟨structured verdict parsed — rendered above⟩

The prover resolves the assigned continuous problem. The reduction establishes $\mathrm{NP}$-hardness for variable support size with $m=1$, including all permitted fractional interventions. The exact algorithm and its stated running time are also justified. I found no major or minor issues.

1. Normal-form lemma

The replacement $p_u\leftarrow s_u$ for initial nonvoters is valid in both cases: $s_u=0$ forces the original $p_u=0$, while $s_u>0$ permits the new choice $p_u=s_u\leq1$.

The replacement preserves every numerator and weakly decreases every denominator. Each denominator remains strictly positive because initial voters retain voting fraction one and contribute $d_t>0$. Nonnegative numerators therefore ensure that ratings weakly increase. Cost and feasibility remain unchanged, so revenue cannot decrease.

The converse assertion is also correct: every normalized point with $x_u\in[0,1]$ gives an allowed intervention, including the endpoint $x_u=0$. Thus the normalization preserves the existence of a witness meeting any revenue threshold.

The unchanged intervention has zero cost and zero revenue, validating the assertion for $\rho\leq0$.

2. Reduction instance and domain requirements

The restriction of CLIQUE to $n\geq2$ and $2\leq k\leq n$ only removes immediately decidable cases.

All constructed masses are positive and sum to one. There are $n+1$ initial voters and $n$ initial nonvoters, so the required condition $\varnothing\ne V\subsetneq T$ holds.

The kernel is symmetric and nonnegative, with strictly positive diagonal. Every type has positive weighted access to an initial voter, including the isolated anchor through its self-connection.

The degree bound gives
$$ H_i=2d_i+\frac43\leq2n-\frac23<2n, $$
so the stated weaker bound is valid. Initial ratings are exactly as claimed, giving $U_0=b(n+2k)$.

3. Exact ratings, cost, and revenue

Substitution of the masses and kernel entries gives the displayed formulas for $R_{u_i}$ and $R_{v_i}$. In particular, the denominator of $R_{v_i}$ contains both the diagonal perturbation $\varepsilon h_i$ and the neighboring-voter contribution $\varepsilon d_i$, yielding $\varepsilon H_i$.

The anchor cannot change and maintains rating one. Its population-weighted utility contribution cancels $U_0$. The remaining cost is exactly
$$ C=b\sum_i(3z_i+x_i), $$
and the budget and revenue formulas follow without omitted contributions.

At $\varepsilon=0$, the displayed function $g$ is correct, and both specified endpoint choices have value one and the stated costs.

4. Fractional rounding

The identity
$$ 1-g(z,x)=zx+(1-z)\frac{(1-x)^2}{1+x} $$
checks algebraically. Its terms are nonnegative on the entire box. The endpoint formulas for the affine dependence on $z$ also verify $g\geq0$, hence $0\leq\delta\leq1$.

Both branches of the rounding proof are valid, including the boundary $x=1/2$, which belongs to the first branch. The constants $6$, $4$, and $10$ in that branch, and the square-root estimate in the second branch, are justified by the displayed inequalities.

Cauchy–Schwarz gives the stated aggregate bound
$$ \ell\leq10\sqrt{n\Delta}. $$
Changing the normalized cost contributes at most $3\ell$. Therefore feasibility together with $3\ell<2$ indeed forces $|S|\leq k$, using the integrality of $|S|$. No integrality assumption is imposed on the original intervention.

5. Perturbation and Lipschitz estimates

All $r_i$ lie in $[0,1]$, so $|K_i|\leq H_i$ holds. The exact identity for $R_{v_i}$ and the subsequent remainder formula are algebraically correct.

Since $D_i\geq1$ and $\varepsilon H_i\geq0$, the bounds
$$ |G_\varepsilon-G_0|\leq6\varepsilon n^2, \qquad |\mathcal R|\leq12\varepsilon^2n^3 $$
hold uniformly throughout the intervention box.

The derivatives of $r_i$ are correct and bounded as claimed. The bounds for differences of $K_i$ and $K_i/D_i$ follow from those estimates and positive denominators. When summed, the neighboring contributions count each $\ell_j$ exactly $d_j$ times because the graph is undirected. The resulting Lipschitz constant $21n$ is valid.

6. Edge-counting identity

For vertices inside and outside $S$, both displayed expressions for $3K_i/D_i$ check.

Crossing edges contribute $-3$ each, edges outside $S$ contribute $-3$ each, and internal edges contribute zero. The additional constant contribution is $-(n-|S|)$. Consequently,
$$ Q(S)=3E(S)+|S|-3M-n $$
is correct.

A $k$-clique gives $Q(S)=I$. In a graph without a $k$-clique, a set of size $k$ loses at least three relative to $I$. For smaller sets, the stated increment of $f$ verifies the weaker bound $Q(S)\leq I-1$. This argument includes $S=\varnothing$.

7. Threshold separation

The clique intervention exactly meets the budget. Its remainder bound gives the required strict excess over the threshold, since $12\varepsilon n^3<1/4$.

For the converse, the lower bound $I-1/2\geq-3n^2$ is valid throughout the specified range. Combining it with the uniform perturbation estimate gives $\Delta\leq9\varepsilon n^2$ and hence the claimed bound on $\ell$.

The selected $\varepsilon$ ensures $3\ell<2$, so rounding produces $|S|\leq k$. The no-clique bound for $Q(S)$ is therefore applicable. Finally,
$$ 21n\ell+12\varepsilon n^3 \leq \frac{630}{10^4n^{3/2}}+\frac{12}{10^8n^5} <\frac14 $$
holds already at $n=2$ and decreases thereafter. The resulting upper bound is strictly below the decision threshold, contradicting even a witness attaining equality.

Thus the proof excludes all real fractional witnesses in no-instances.

8. Encoding and reduction complexity

The construction has $m=1$ and $\tau=2n+1$. Every constructed rational has binary length $O(\log n)$, including the perturbation-dependent kernel entries and threshold. Listing the full kernel therefore gives $L=O(n^2\log n)$ and polynomial construction time.

The threshold is strictly positive by the displayed lower bound. The reduction is a valid polynomial-time many-one reduction.

9. Exact algorithm

The normalized formulation uses $\tau$ intervention variables and $\tau$ rating variables. It has $O(\tau)$ constraints of degree at most two.

Every $D_t$ is strictly positive on the intervention box, so the equations determine exactly the intended ratings; they introduce no spurious witnesses. Rational computation of $U_0$ and denominator clearing have polynomial bit complexity and produce coefficients of polynomial bit length in $L$.

The cited theorem supports the application: with one quantified block and no free variables, its arithmetic-operation and intermediate integer-size bounds yield $(sd)^{O(q)}B^{O(1)}$ bit complexity. Substituting $q=2\tau$, $s=O(\tau)$, and $d=2$ gives the claimed $\tau^{O(\tau)}L^{O(1)}$ bound. [Basu’s survey, Theorem 2.18](https://www.math.purdue.edu/~sbasu/raag_survey2011_final.pdf).

Polynomial-time solvability for fixed $\tau$ and membership in $\exists\mathbb R$ follow. The prover appropriately claims $\mathrm{NP}$-hardness, without claiming $\mathrm{NP}$ membership or completeness.

No additional clarification is needed.

⟨structured verdict parsed — rendered above⟩