d4-conf-ijcai-2017-0625 (d4-conf-ijcai-2017-0625)

Given annotation-task types \(T\) with rational masses \(\mu_t\), two predictions \(a_t,b_t\in\mathcal K\), and type-level label distributions \(\pi_t\), let \(D=\{t:a_t\ne b_t\}\). For a target expected accuracy \(\theta\), choose validated masses \(x_t\) minimizing \(\sum_{t\in T}x_t\), subject to \(0\le x_t\le\mu_t\), \(x_t=0\) for \(t\notin D\), and \(\sum_{t\in T}[x_t+(\mu_t-x_t)\pi_t(a_t)]\ge\theta\); report an optimal allocation or infeasibility.

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.
Let \(\mathcal K\) be a label set of size \(m\ge2\). Each type has fixed predictions \(a_t,b_t\in\mathcal K\) and an explicitly given rational distribution \(\pi_t\) over its true label. All numerical inputs are encoded in binary; \(L\) is the total input bit length.
For \(t\sim\mu\) and \(Y\sim\pi_t\), assume the events \(a_t\ne Y\) and \(b_t\ne Y\) are independent, with accuracies \(p_a=\sum_t\mu_t\pi_t(a_t)\) and \(p_b=\sum_t\mu_t\pi_t(b_t)\) satisfying \(0<p_a<1\) and \(p_b>1/2\).
Set \(D=\{t:a_t\ne b_t\}\). Validation reveals the true label perfectly, costs one per unit mass, and leaves unvalidated predictions and label distributions fixed; any selected portion of a type has the same true-label distribution \(\pi_t\).
Given rational \(\theta\in[0,1]\), minimize \(\sum_{t\in T}x_t\) over divisible validated masses satisfying \(0\le x_t\le\mu_t\), \(x_t=0\) for \(t\notin D\), and \(\sum_{t\in T}[x_t+(\mu_t-x_t)\pi_t(a_t)]\ge\theta\); return an optimal allocation or infeasibility.

Is this continuous minimum-validation problem solvable exactly in polynomial time in \(m,\tau,L\), or is its budget decision version, with an additional binary-rational bound \(B\in[0,1]\) on \(\sum_t x_t\), \(\mathrm{NP}\)-hard?

For finite instances, disagreement selection has a strictly higher misclassification probability than uniform selection under independent error events and the stated accuracy conditions; this is a probabilistic result, not a complexity classification ([source](https://www.ijcai.org/proceedings/2017/0324.pdf)).
No prior result settling exactly the continuous optimization problem above was identified in the search.

Result

The continuous minimum-validation problem is exactly solvable in polynomial time in \(m,\tau,L\). Its budget decision version belongs to \(\mathrm{P}\).

An optimal allocation is obtained by validating eligible types in decreasing order of \(1-\pi_t(a_t)\), stopping when the target accuracy is reached. At most one type needs to be partially validated. The proof below includes an exact rational algorithm and its bit-complexity bound.

1. Reduction to a linear covering problem

For every type \(t\), define its initial accuracy and its gain per unit of validated mass by

\(q_t=\pi_t(a_t),\qquad g_t=1-q_t.\)

Because \(\pi_t\) is a probability distribution, \(0\le g_t\le1\). The assumption that every selected portion retains the distribution \(\pi_t\) gives

\(x_t+(\mu_t-x_t)\pi_t(a_t)=\mu_tq_t+g_tx_t.\)

Consequently, the accuracy after validation is exactly

\(p_a+\sum_{t\in D}g_tx_t.\)

Put \(\delta=\theta-p_a\). The optimization problem becomes

\(\displaystyle \min\sum_{t\in D}x_t \quad\text{subject to}\quad \sum_{t\in D}g_tx_t\ge\delta,\qquad 0\le x_t\le\mu_t.\)

Coordinates outside \(D\) are fixed at zero, as required.

If \(\delta\le0\), the zero allocation is feasible and optimal because every allocation has nonnegative cost. Henceforth suppose \(\delta>0\).

Types with \(g_t=0\) contribute no accuracy gain. Setting their allocations to zero preserves feasibility and weakly decreases cost. Thus they can be omitted.

2. Exact algorithm and feasibility

List the types in \(D\) having positive gain as \(t_1,\ldots,t_n\), ordered so that

\(g_{t_1}\ge g_{t_2}\ge\cdots\ge g_{t_n}>0.\)

Ties may be broken arbitrarily. Write \(g_i=g_{t_i}\), \(\mu_i=\mu_{t_i}\), and define

\(S_0=0,\qquad S_j=\sum_{i=1}^{j}\mu_i g_i\quad(1\le j\le n).\)

For any permissible allocation,

\(\displaystyle \sum_{t\in D}g_tx_t\le\sum_{t\in D}g_t\mu_t=S_n.\)

Conversely, validating every eligible positive-gain type attains gain \(S_n\). Therefore:

The instance is feasible if and only if \(\delta\le S_n\).

This also handles \(n=0\): then \(S_n=0\), so an instance with \(\delta>0\) is infeasible.

For a feasible instance with \(\delta>0\), let \(k\) be the smallest index satisfying \(S_k\ge\delta\). Define

\(\displaystyle x^*_{t_i}= \begin{cases} \mu_i,&i<k,\\ (\delta-S_{k-1})/g_k,&i=k,\\ 0,&i>k, \end{cases}\)

and set every other coordinate to zero.

Minimality of \(k\) gives

\(S_{k-1}<\delta\le S_{k-1}+\mu_k g_k.\)

Since \(g_k>0\), this implies \(0<x^*_{t_k}\le\mu_k\). Thus all mass bounds hold. Moreover,

\(\displaystyle \sum_{t\in D}g_tx_t^* =S_{k-1}+g_k\frac{\delta-S_{k-1}}{g_k} =\delta.\)

The allocation is therefore feasible, with cost

\(\displaystyle C^*=\sum_{i<k}\mu_i+\frac{\delta-S_{k-1}}{g_k}.\)

3. Proof of optimality

Let \(y\) be any feasible allocation. Define the mass it validates among positive-gain eligible types by

\(\displaystyle C_+(y)=\sum_{i=1}^{n}y_{t_i}.\)

Its total cost is at least \(C_+(y)\). Since all other eligible types have zero gain, feasibility implies

\(\displaystyle \delta\le\sum_{i=1}^{n}g_i y_{t_i}.\)

Decompose this gain around \(g_k\):

\(\displaystyle \sum_{i=1}^{n}g_i y_{t_i} =g_k C_+(y)+\sum_{i=1}^{n}(g_i-g_k)y_{t_i}.\)

For \(i<k\), the coefficient \(g_i-g_k\) is nonnegative, so the bound \(y_{t_i}\le\mu_i\) gives

\((g_i-g_k)y_{t_i}\le(g_i-g_k)\mu_i.\)

For \(i\ge k\), the coefficient is nonpositive and \(y_{t_i}\ge0\), so

\((g_i-g_k)y_{t_i}\le0.\)

Combining these inequalities yields

\(\displaystyle \delta\le g_k C_+(y)+\sum_{i<k}(g_i-g_k)\mu_i =g_k C_+(y)+S_{k-1}-g_k\sum_{i<k}\mu_i.\)

Division by the positive number \(g_k\) gives

\(\displaystyle C_+(y)\ge \sum_{i<k}\mu_i+\frac{\delta-S_{k-1}}{g_k} =C^*.\)

Therefore every feasible allocation has total cost at least \(C^*\), and the constructed allocation attains this bound. This proves optimality, including when gains are tied.

4. Exact arithmetic and polynomial bit complexity

It remains to ensure that the algorithm is polynomial in the binary input length, rather than merely using polynomially many arithmetic operations.

Represent each input rational by an integer numerator and a positive integer denominator. Let \(Q\) be the product of all input denominators, including that of \(B\) for the decision version. Because their total encoded length is at most \(L\), the binary length of \(Q\) is \(O(L)\).

All input rationals can be expressed over \(Q\). In particular, write

\(\mu_t=M_t/Q,\qquad q_t=U_t/Q,\qquad g_t=G_t/Q,\qquad \theta=H/Q,\)

where \(G_t=Q-U_t\). These integers satisfy

\(0\le U_t,G_t,H\le Q,\qquad M_t>0,\qquad \sum_tM_t=Q.\)

Define integers

\(\displaystyle P=\sum_tM_tU_t,\qquad R=HQ-P,\qquad W_j=\sum_{i=1}^{j}M_{t_i}G_{t_i}.\)

Then

\(p_a=P/Q^2,\qquad \delta=R/Q^2,\qquad S_j=W_j/Q^2.\)

The nonnegative integers \(P\) and \(W_j\) are at most \(Q^2\), because \(U_t,G_t\le Q\) and \(\sum_tM_t=Q\). Also \(|R|\le Q^2\). Hence all have \(O(L)\) bits.

Sorting gains amounts to sorting the integers \(G_t\). Feasibility and the stopping index are determined by integer comparisons. The sole potentially partial coordinate is

\(\displaystyle x^*_{t_k}=\frac{R-W_{k-1}}{QG_{t_k}},\)

whose numerator and denominator have \(O(L)\) bits. The optimum cost can likewise be computed directly as

\(\displaystyle C^*= \frac{G_{t_k}\sum_{i<k}M_{t_i}+R-W_{k-1}} {QG_{t_k}}.\)

Its numerator and denominator also have \(O(L)\) bits. Exact output uses numerator–denominator representations; divisibility of the allocation does not require terminating binary expansions.

Constructing \(Q\), converting the inputs, sorting at most \(\tau\) gains, computing prefix sums, and producing the allocation all require polynomially many operations on integers of polynomial bit length. Integer arithmetic therefore gives an exact polynomial-time algorithm. There is no enumeration of types beyond the explicitly supplied support.

5. Budget decision and probabilistic assumptions

For the budget decision version, return “yes” exactly when the optimization instance is feasible and \(C^*\le B\). This comparison is exact by cross-multiplication of rational numerators and positive denominators. Thus the budget decision problem belongs to \(\mathrm{P}\); an \(\mathrm{NP}\)-hardness classification under polynomial-time many-one reductions would imply \(\mathrm{P}=\mathrm{NP}\).

The optimization proof requires neither independence of the error events nor the stated accuracy inequalities. It applies to all instances with the given fixed distributions and divisible allocations, and hence to the promised instances in the question. The cited paper’s Theorem 1 concerns the increased probability of selecting a misclassified instance through disagreement selection. ([Source](https://www.ijcai.org/proceedings/2017/0324.pdf)) The complexity classification here follows from the explicit linear gain structure proved above.

⟨structured verdict parsed — rendered above⟩

The prover resolves the assigned problem correctly: the continuous optimization admits an exact polynomial-time algorithm, and its budget decision version belongs to \(\mathrm{P}\). No major or minor mathematical issues were found.

• Reduction to the stated optimization problem.

The definitions \(q_t=\pi_t(a_t)\) and \(g_t=1-q_t\) give \(0\le g_t\le1\). The identity
\[ x_t+(\mu_t-x_t)q_t=\mu_tq_t+g_tx_t \]
correctly accounts for perfect validation and the unchanged distribution of unvalidated mass.

Summing over the support gives the initial accuracy \(p_a\) plus \(\sum_{t\in D}g_tx_t\), since allocations outside \(D\) are constrained to zero. Thus the covering constraint with \(\delta=\theta-p_a\) is exactly equivalent to the original accuracy constraint. The objective and coordinate bounds are preserved.

• Nonpositive targets and zero-gain types.

If \(\delta\le0\), the zero allocation is feasible and has minimum possible cost, namely zero. This includes equality.

Setting a zero-gain coordinate to zero preserves accuracy and cannot increase cost. Omitting such coordinates therefore preserves the optimum and feasibility. No division by a zero gain occurs later.

• Feasibility characterization.

For every permissible allocation, nonnegative gains and the coordinate bounds imply
\[ \sum_{t\in D}g_tx_t\le\sum_{t\in D}g_t\mu_t=S_n. \]
Full validation of all eligible positive-gain types attains this upper bound. Consequently, the criterion \(\delta\le S_n\) is both necessary and sufficient.

The empty eligible list is explicitly handled: \(S_0=0\), so a positive required gain is infeasible.

• Construction and boundary cases.

For a feasible instance with \(\delta>0\), the stopping index \(k\) exists. Its minimality implies
\[ S_{k-1}<\delta\le S_{k-1}+\mu_kg_k. \]
Since \(g_k>0\), the proposed stopping coordinate lies in \((0,\mu_k]\). All other coordinates satisfy their bounds and eligibility restrictions.

Substitution verifies that the constructed gain is exactly \(\delta\), and summing its coordinates gives the displayed cost \(C^*\). If \(\delta=S_k\), the stopping coordinate is fully validated; hence the statement that *at most* one type is partially validated remains correct. The construction also handles \(k=1\) and \(\delta=S_n\).

• Optimality proof.

The argument applies to every feasible allocation \(y\), including allocations that waste mass on zero-gain types. Its total cost is at least \(C_+(y)\).

The decomposition around \(g_k\) is an exact algebraic identity. Sorting ensures \(g_i-g_k\ge0\) for \(i<k\) and \(g_i-g_k\le0\) for \(i\ge k\). The prover therefore uses the appropriate coordinate bounds in each case, with the inequality directions correct.

Combining those bounds with feasibility yields
\[ \delta\le g_kC_+(y)+S_{k-1}-g_k\sum_{i<k}\mu_i. \]
Division by the strictly positive \(g_k\) gives \(C_+(y)\ge C^*\). Since the constructed allocation attains \(C^*\), this proves global optimality. Equal gains cause no difficulty: the corresponding coefficients vanish.

• Exact arithmetic and bit complexity.

Under the stated binary encoding of rational numerators and denominators, the product \(Q\) of input denominators has \(O(L)\) bits: its logarithm is bounded by the sum of the denominator encoding lengths. Every input denominator divides \(Q\), so the common-denominator conversions are exact.

The formulas for \(P,R,W_j\), and their denominators are correct. The bounds \(P,W_j\le Q^2\) follow from \(\sum_tM_t=Q\) and \(U_t,G_t\le Q\); likewise, \(|R|\le Q^2\).

Substitution into the stopping coordinate and cost reproduces both displayed rational formulas. Their numerators and denominators have \(O(L)\) bits, and their denominators are positive. The full allocation consequently has polynomial output length.

Constructing the common denominator, converting inputs, sorting gains, accumulating sums, and outputting coordinates require polynomially many operations on polynomial-length integers. The algorithm processes only the explicitly supplied support. This establishes the requested polynomial bound in \(m,\tau,L\), rather than merely an arithmetic-operation bound.

• Budget decision and probabilistic context.

For a feasible instance, a budget-feasible allocation exists exactly when its minimum cost is at most \(B\). Rational cross-multiplication gives an exact polynomial-time comparison. In the already handled case \(\delta\le0\), the optimum is zero and every permitted \(B\ge0\) suffices.

The conditional statement about \(\mathrm{NP}\)-hardness and \(\mathrm{P}=\mathrm{NP}\) is correct for polynomial-time many-one reductions.

Independence and the accuracy promises are unnecessary for this optimization proof, so their omission from its algebra strengthens rather than restricts its applicability. The description of the cited probabilistic result matches [Theorem 1 and its accompanying independence assumption](https://www.ijcai.org/proceedings/2017/0324.pdf). That theorem is contextual and is not used to establish complexity.

No additional clarification, missing lemma, or repair is needed.

⟨structured verdict parsed — rendered above⟩