Answer: \(\mathrm{NP}\)-hard in the proper-learning sense: a learner with the requested polynomial time and sample bounds would imply \(\mathrm{NP}=\mathrm{RP}\). Polynomial sample complexity alone is possible.
Theorem 4.2 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateNetwork flow functions are not efficiently learnable unless $\NP = \RP$.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a known directed topology with one edge-agent location \(e_t\) per type \(t\in T\), rational population masses \(\mu_t\) with \(\sum_t\mu_t=1\), and unknown per-agent capacities \(a_t\), draw i.i.d. mass-coalition samples \(z_j\in\prod_{t\in T}[0,\mu_t]\) from an unknown \(\mathcal D\), labeled by \(F_a(z_j)=\operatorname{maxflow}(G(a\odot z),s,\mathrm{sink})\). Output a proper \(\widehat a\) with time and sample complexity polynomial in \(\tau=|T|\), input length, \(1/\varepsilon\), and \(\log(1/\delta)\), such that with probability at least \(1-\delta\), \(\Pr_{z\sim\mathcal D}[F_{\widehat a}(z)\ne F_a(z)]\le\varepsilon\).
A society is given by its support: the list of \(\tau\) types with positive masses \(\mu_t\), each a binary rational, with \(\sum_{t\in T}\mu_t=1\). Here \(\tau=|T|\) counts supported types, not possible types.
The known topology is a finite directed multigraph \(G=(V,E)\), with distinct source \(s\) and sink \(r\), and a bijection \(t\mapsto e_t\) from \(T\) to \(E\). Parallel edges are allowed; set \(m=|V|+|E|\).
Unknown per-agent capacities are \(a\in\mathbb Q_{\ge0}^{\tau}\). For a mass coalition \(z\in\prod_{t\in T}[0,\mu_t]\), edge \(e_t\) has capacity \(a_tz_t\); let \(F_a(z)\) be the maximum \(s\)-\(r\) flow.
Use the binary encoding model: a supplied bound \(L\) bounds the encoding length of each mass, target capacity, sample coordinate, and label. The unknown distribution \(\mathcal D\) is arbitrary over rational mass coalitions obeying this bound, including distributions with atoms.
Given \(\varepsilon,\delta\in(0,1)\) and access only to i.i.d. labeled samples \((z,F_a(z))\), a proper learner outputs \(\widehat a\in\mathbb Q_{\ge0}^{\tau}\) on the same topology such that \(\Pr[\Pr_{z\sim\mathcal D}[F_{\widehat a}(z)\ne F_a(z)]\le\varepsilon]\ge1-\delta\), where the outer probability includes sampling and learner randomness.
Is this distribution-free proper PAC learning problem solvable with time and sample complexity polynomial in \(m,\tau,L,1/\varepsilon,\log(1/\delta)\), or is it \(\mathrm{NP}\)-hard?
For discrete edge coalitions, distribution-free proper PAC learning of network-flow functions is not efficient unless \(\mathrm{NP}=\mathrm{RP}\); it is efficient when the distribution is supported on source–sink paths. [Verified results](https://arxiv.org/pdf/1505.00039v2).
No result settling exactly the mass-coalition learning problem above was located.
The problem is computationally hard: a proper PAC learner with the requested polynomial bounds would imply \(\mathrm{NP}=\mathrm{RP}\). This holds even for an acyclic topology with four vertices, dyadic masses and sample coordinates, and labels in \(\{0,1\}\).
Precisely, finite-sample consistency is \(\mathrm{NP}\)-hard under a deterministic reduction, and an efficient proper PAC learner would give a one-sided randomized polynomial-time algorithm for that hard problem. Polynomial sample complexity alone is possible.
We use the standard theorem that three-colourability of finite simple undirected graphs is \(\mathrm{NP}\)-complete. [Garey, Johnson and Stockmeyer](https://doi.org/10.1016/0304-3975%2876%2990059-1).
Let \(H=(U,A)\) be such a graph, with \(n=|U|\geq 1\). Construct a directed network with vertices \(v_0,v_1,v_2,v_3\), source \(s=v_0\), and sink \(r=v_3\).
For every \(i\in\{1,2,3\}\) and \(u\in U\), introduce an edge \(e_{i,u}\) from \(v_{i-1}\) to \(v_i\). Thus the network consists of three bundles of parallel edges in series. Add one dummy edge \(e_*\) from \(v_0\) to \(v_1\).
There is one supported type per edge. Set
\(Q=2^{\lceil\log_2(3n+1)\rceil}\),
and assign masses
\(\mu_{i,u}=1/Q,\qquad \mu_*=1-3n/Q.\)
All masses are positive dyadic rationals, and their sum is one. The parameters are \(\tau=3n+1\) and \(m=3n+5\).
For each \(S\subseteq U\), define a coalition \(z^S\) by
\(z^S_{i,u}=1/Q\) if \(u\in S\), and \(z^S_{i,u}=0\) otherwise; also set \(z^S_*=0\).
These coordinates satisfy the required mass bounds.
For any nonnegative capacity vector \(a\), put \(w_i(u)=a_{i,u}/Q\). Then
\(F_a(z^S)=\min_{i\in\{1,2,3\}}\sum_{u\in S}w_i(u).\) \((1)\)
Indeed, the total capacity of bundle \(i\) is the corresponding sum, and every flow must cross all three bundles. Conversely, any value at most all three bundle totals can be allocated among the parallel edges of each bundle. The allocations satisfy conservation at the two intermediate vertices because each bundle carries the same total. The dummy edge has zero capacity on these coalitions.
Construct the following labeled examples:
Let \(K=n+|A|\) be their number.
Lemma. The constructed examples admit a consistent nonnegative rational capacity vector if and only if \(H\) is three-colourable. In the forward construction, each capacity belongs to \(\{0,Q\}\).
Proof. First suppose \(c:U\to\{1,2,3\}\) is a proper colouring. Define
\(a_{i,u}=0\) when \(i=c(u)\), and \(a_{i,u}=Q\) otherwise; set \(a_*=0\).
For a singleton \(\{u\}\), one bundle has capacity zero, so its label is zero.
For an edge \(\{u,v\}\), the colours differ. Consequently, the three bundle capacities on \(z^{\{u,v\}}\) are \(1,1,2\), in some order. Equation \((1)\) gives flow one. Hence every example is fitted.
Conversely, suppose a nonnegative rational vector \(a\) fits every example. Each singleton example gives
\(\min_i w_i(u)=0.\)
Because all weights are nonnegative and there are three of them, at least one is exactly zero. Choose one such index as \(c(u)\).
For each graph edge \(\{u,v\}\), its example gives
\(\min_i\bigl(w_i(u)+w_i(v)\bigr)=1.\)
Thus every bundle sum is at least one. If \(c(u)=c(v)=i\), both weights in that bundle would be zero, contradicting this inequality. Therefore \(c\) is a proper three-colouring. This proves the lemma.
Every mass, sample coordinate, label, and capacity in the constructed realizing target has encoding length \(O(\log(n+1))\). Choose a supplied bound \(L\) large enough for those encodings. Thus consistency is already \(\mathrm{NP}\)-hard on instances satisfying the stipulated binary encoding bounds.
Suppose a learner \(\mathcal A\) has the requested polynomial time and sample bounds. We construct an RP algorithm for three-colourability.
Let \(R=2^{\lceil\log_2 K\rceil}\). Pad the example list to length \(R\) by repeating its first example, and sample uniformly from this padded list. Sampling requires exactly \(\log_2 R\) independent random bits. Every distinct example has probability at least \(1/R\).
Run \(\mathcal A\) with
\(\varepsilon=1/(2R),\qquad \delta=1/4,\)
using this sampling procedure. Verify that its output is a nonnegative rational vector and fits all \(K\) distinct examples. Accept precisely when verification succeeds.
All parameters are polynomially bounded in the input size: \(R\leq 2K\), \(K=O(n^2)\), and \(L=O(\log(n+1))\). Verification uses equation \((1)\), so it consists of polynomially many exact rational additions and comparisons. A polynomial-time learner can output only polynomially many bits.
To handle inputs outside the learner’s realizability promise, stop it after its polynomial running-time bound and reject if it has not produced a valid output.
If \(H\) is three-colourable, the lemma supplies a target with capacities in \(\{0,Q\}\), obeying \(L\), whose labels agree with the sampling procedure. The samples are therefore genuinely i.i.d. labeled samples from an admissible target and distribution.
With probability at least \(3/4\), the learner’s error is at most \(1/(2R)\). But disagreement on even one constructed example would have probability at least \(1/R\). Hence a successful output fits every example, and verification accepts.
If \(H\) is not three-colourable, the lemma shows that no proper output can fit every example. Verification therefore rejects for every sampling sequence and every choice of learner randomness. No learning guarantee on unrealizable inputs is needed.
This is a polynomial-time randomized decision algorithm with no false acceptances and acceptance probability at least \(3/4\) on yes-instances. Thus three-colourability belongs to \(\mathrm{RP}\). Its \(\mathrm{NP}\)-completeness, together with \(\mathrm{RP}\subseteq\mathrm{NP}\), yields \(\mathrm{NP}=\mathrm{RP}\).
For completeness, the encoding bound makes the target class finite.
Let \(\mathcal H_L\) contain all capacity vectors whose coordinates have valid encodings of length at most \(L\). There are fewer than \(2^{L+1}\) possible bit strings per coordinate, so
\(|\mathcal H_L|\leq 2^{\tau(L+1)}.\)
An exhaustive learner can enumerate this class and return any hypothesis consistent with its samples. The target itself belongs to the class, so such a hypothesis exists.
For any fixed hypothesis with disagreement probability greater than \(\varepsilon\), the probability of consistency with \(N\) independent samples is at most
\((1-\varepsilon)^N\leq e^{-\varepsilon N}.\)
A union bound shows that the probability that any such hypothesis is consistent is at most \(|\mathcal H_L|e^{-\varepsilon N}\). Therefore it suffices to take
\(N=\left\lceil\bigl(\tau(L+1)\ln 2+\ln(1/\delta)\bigr)/\varepsilon\right\rceil.\)
This proves polynomial sample complexity for exact equality loss, including distributions with atoms. The reduction above establishes the computational obstruction.
⟨structured verdict parsed — rendered above⟩
Verdict: proved. The reduction establishes that a proper PAC learner with the requested polynomial time and sample bounds would imply \(\mathrm{NP}=\mathrm{RP}\). The polynomial sample bound is also correct. I found no major or minor mathematical issues.
The hardness statement has the appropriate scope: finite-sample consistency is deterministically \(\mathrm{NP}\)-hard, and efficient proper PAC learning would yield an \(\mathrm{RP}\) algorithm for three-colourability.
The cited theorem—that three-colourability of finite simple undirected graphs is \(\mathrm{NP}\)-complete—is correct. The cited paper establishes hardness even with additional graph restrictions, so its application to unrestricted finite simple graphs is valid. [Garey, Johnson and Stockmeyer](https://doi.org/10.1016/0304-3975%2876%2990059-1).
Restricting the reduction to \(\,n\geq1\,\) excludes only the trivial empty graph and does not affect hardness.
The constructed network satisfies the task:
The mass construction is valid. Since \(\,Q\geq3n+1\,\), the dummy mass satisfies
\[
\mu_*=\frac{Q-3n}{Q}>0.
\]
All masses are dyadic rationals, and their sum is exactly one.
Every coalition coordinate respects its mass bound: an ordinary coordinate is either zero or its type’s full mass, while the dummy coordinate is zero.
The construction also has polynomial encoding size. The bound
\[
3n+1\leq Q<2(3n+1)
\]
ensures that the masses, coalition coordinates, labels, and realizing capacities have encoding length \(\,O(\log(n+1))\,\). Writing all coordinates of all examples still requires only polynomially many bits.
Equation \(\,(1)\,\) is correct for every nonnegative capacity vector on the constructed coalitions.
Each bundle’s total capacity is
\[
\sum_{u\in S}w_i(u).
\]
Every source–sink flow must pass through all three bundles, so its value cannot exceed their minimum.
The converse argument is sufficient: any nonnegative value at most all three totals can be distributed among the parallel edges in each bundle. Using the same total in every bundle satisfies conservation at both intermediate vertices.
The dummy edge has zero capacity because its coalition coordinate is zero. Thus its unknown per-agent capacity does not affect this formula.
The proposed capacity vector is nonnegative, rational, and within the stated encoding bound.
For a singleton coalition, the bundle indexed by the vertex’s colour has zero capacity, so the minimum bundle total is zero.
For an edge coalition, proper colouring gives two distinct colours. The corresponding bundle totals are exactly \(\,1,1,2\,\), so the flow equals one.
This verifies every prescribed label, including singleton examples for isolated vertices.
The singleton constraint gives
\[
\min_i w_i(u)=0.
\]
Because all three weights are nonnegative, at least one is exactly zero. Choosing any zero index therefore defines a colour for every vertex.
The edge constraint gives
\[
\min_i\bigl(w_i(u)+w_i(v)\bigr)=1,
\]
which implies that every bundle sum is at least one. If adjacent vertices receive the same chosen index, that bundle sum is zero, a contradiction.
The argument remains valid when a vertex has several zero weights: any selected zero index obeys the same contradiction on every incident edge.
Consequently, the equivalence holds for arbitrary nonnegative rational candidate capacities, not merely for capacities in the construction’s two-element set. This is essential for rejecting arbitrary proper learner outputs.
The consistency hardness conclusion follows from the polynomial deterministic reduction.
The sampling construction is valid. Since \(\,K\geq1\,\), the padded list exists, and
\[
K\leq R\leq2K.
\]
Uniformly sampling independent indices gives i.i.d. examples. Every distinct example has probability at least \(\,1/R\,\). When \(\,K=1\,\), sampling requires zero random bits; this causes no problem.
On a colourable graph, the consistency lemma supplies an admissible target with capacities in \(\,\{0,Q\}\,\). Thus the simulated labels really are evaluations of one allowed target under one allowed distribution. The learner’s realizability guarantee applies.
With probability at least \(\,3/4\,\), the output’s disagreement probability is at most \(\,1/(2R)\,\). Any disagreement on a listed example would instead have probability at least \(\,1/R\,\). Therefore every successful output fits the entire list.
On a non-colourable graph, the consistency lemma rules out every nonnegative rational vector fitting the list. Verification consequently prevents false acceptance, irrespective of the learner’s behaviour on unrealizable data.
The runtime argument is also sound:
The resulting decision procedure has one-sided error and acceptance probability at least \(\,3/4\,\) on yes-instances. Hence three-colourability belongs to \(\mathrm{RP}\). Its \(\mathrm{NP}\)-completeness and the standard inclusion \(\mathrm{RP}\subseteq\mathrm{NP}\) give the claimed equality.
The finite-class argument correctly uses the task’s bound on each target-capacity encoding.
There are fewer than \(\,2^{L+1}\,\) bit strings of length at most \(\,L\,\). Restricting to valid nonnegative rational encodings can only decrease this number, so
\[
|\mathcal H_L|\leq2^{\tau(L+1)}.
\]
Duplicate encodings or vectors defining identical functions do not invalidate this upper bound.
The target belongs to the enumerated class, guaranteeing the existence of a consistent hypothesis. Exhaustive enumeration therefore gives a proper learner, with no claim of efficient computation.
For a fixed hypothesis with disagreement probability greater than \(\,\varepsilon\,\), independence bounds its probability of fitting every sample by
\[
(1-\varepsilon)^N\leq e^{-\varepsilon N}.
\]
The union bound and the stated choice of \(\,N\,\) give failure probability at most \(\,\delta\,\).
This reasoning applies to exact equality loss and arbitrary admissible distributions, including distributions with atoms.
No repair or additional clarification is required. The computational obstruction and polynomial sample-complexity claim both follow from the written argument.
⟨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.