Answer: polynomial-time solvable (in \(\mathrm{P}\)) for every fixed \(\ell\ge 4\)
Theorem 3.8 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateFor ∆> 1, BOUNDED POWER is NP- complete for every fixed ℓ≥4.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite type set \(T\), rational masses \(\mu_t\), voting and delegating costs \(v_t\) and \(d_t\), an approved type relation \(A\), a per-capita budget \(b\), and \(L=4\), decide whether a complete type-role blow-up admits a measurable delegation policy that partitions each type mass into casting and noncasting mass, assigns exactly one approved outgoing edge to every noncasting voter, routes every delegation along an edge-respecting path ending at casting mass, gives each type-\(u\) casting mass total represented mass at most \(L\) times its casting mass, and has total normalized cost \(\sum_t[v_t a_t + d_t(\mu_t-a_t)]\) at most \(b\).
CONTINUOUS BOUNDED POWER. Given finite types \(T\), rational masses \(\mu_t\ge 0\) with \(\sum_{t\in T}\mu_t=1\), an approval relation \(A\subseteq T\times T\), rational costs \(v_t,d_t\), and rational budget \(\bar\beta\), choose casting masses \(y_t\in[0,\mu_t]\). A feasible assignment is nonnegative mass on finite directed \(A\)-paths, including zero-length paths, with total mass starting at \(t\) equal to \(\mu_t\), zero-length mass at \(t\) equal to \(y_t\), and every positive-mass path ending at a type \(s\) with \(y_s>0\). Let \(P_s\) be the total mass of paths ending at \(s\).
For every fixed \(\ell\ge4\), is CONTINUOUS BOUNDED POWER solvable in polynomial time, or is it NP-hard, subject to \(\sum_{t\in T}(v_ty_t+d_t(\mu_t-y_t))\le\bar\beta\) and \(P_t\le\ell y_t\) for all \(t\in T\)?
The discrete BOUNDED POWER problem is NP-complete for every fixed \(\ell\ge4\), even when each voter approves at most two possible delegates. No result for the exact mass formulation above was verified.
Under the formulation in the question, CONTINUOUS BOUNDED POWER is solvable in polynomial time for every fixed \(\ell\ge 4\).
More strongly, the problem remains polynomial-time solvable when a positive rational \(\ell\) is part of the input.
Let \(R^+\subseteq T\times T\) be the positive-path reachability relation:
\((t,s)\in R^+\) if and only if there exists an allowed directed \(A\)-path of positive length starting at \(t\) and ending at \(s\).
The distinction between positive-length and zero-length paths matters on the diagonal. The relation \(R^+\), together with one witness path for every pair in \(R^+\), can be computed in polynomial time by graph search or transitive closure. This also covers whatever convention the model adopts for positive-length paths from \(t\) back to \(t\).
For every \((t,s)\in R^+\), introduce a variable \(x_{ts}\). Its intended meaning is the total mass starting at \(t\) that uses a positive-length path ending at \(s\).
Retain the casting-mass variables \(y_t\). Consider the following system.
For every \(t\in T\),
\(0\le y_t\le \mu_t.\)
For every \((t,s)\in R^+\),
\(x_{ts}\ge 0.\)
All mass starting at \(t\) must either use the zero-length path at \(t\) or a positive-length path:
\(y_t+\sum_{s:(t,s)\in R^+}x_{ts}=\mu_t.\)
The total power received by \(s\) is
\(P_s=y_s+\sum_{t:(t,s)\in R^+}x_{ts}.\)
Consequently, the bounded-power constraint becomes the linear inequality
\(y_s+\sum_{t:(t,s)\in R^+}x_{ts}\le \ell y_s.\)
Finally, the budget constraint is
\(\sum_{t\in T}\bigl(d_t\mu_t+(v_t-d_t)y_t\bigr)\le\bar\beta.\)
Call this rational linear system \(\mathcal L\).
The original instance has a feasible path assignment if and only if \(\mathcal L\) is feasible.
Suppose a feasible path assignment is given. For each \((t,s)\in R^+\), define \(x_{ts}\) as the sum of the masses of all positive-length paths starting at \(t\) and ending at \(s\).
These sums are well-defined because all path masses are nonnegative and the total assigned mass is \(1\).
The total mass starting at \(t\) is \(\mu_t\), while the zero-length mass at \(t\) is exactly \(y_t\). Hence
\(y_t+\sum_{s:(t,s)\in R^+}x_{ts}=\mu_t.\)
Every path ending at \(s\) is either the zero-length path at \(s\), whose mass is \(y_s\), or a positive-length path counted in some \(x_{ts}\). Therefore
\(P_s=y_s+\sum_{t:(t,s)\in R^+}x_{ts}.\)
The original constraint \(P_s\le\ell y_s\) gives the corresponding inequality of \(\mathcal L\). The budget expression is already linear in \(y\). Thus \((x,y)\) is feasible for \(\mathcal L\).
Conversely, suppose \((x,y)\) satisfies \(\mathcal L\).
For every \((t,s)\in R^+\), fix one positive-length witness path \(\pi_{ts}\) from \(t\) to \(s\). Construct an assignment as follows:
The starting-mass equality in \(\mathcal L\) shows that the total mass starting at \(t\) is exactly \(\mu_t\).
It remains to verify the strict endpoint-support condition. Suppose \(x_{ts}>0\). Then the total mass ending at \(s\) satisfies
\(P_s=y_s+\sum_{u:(u,s)\in R^+}x_{us}\ge x_{ts}>0.\)
Because \(\ell>0\) and \(P_s\le\ell y_s\), it follows that
\(y_s\ge P_s/\ell>0.\)
Thus every positive-mass positive-length path ends at a type with positive casting mass. This proves feasibility of the constructed path assignment.
Therefore the two formulations are equivalent.
Let \(n=|T|\). The relation \(R^+\) contains at most \(n^2\) pairs. Hence \(\mathcal L\) has at most \(n+n^2\) variables and \(O(n^2)\) constraints.
All coefficients are rational numbers of polynomial encoding length. In particular, rewriting the budget only requires products such as \(d_t\mu_t\), whose binary encoding length is polynomial in the encoding lengths of the factors.
Feasibility of a rational linear program can be decided in polynomial time. If a feasible assignment must also be produced, a rational feasible LP solution can be found in polynomial time, and the stored witness paths \(\pi_{ts}\) convert it into a path assignment with at most \(n^2+n\) positive-mass paths.
The discrete problem has binary activation decisions: a voter either casts or does not cast. In the continuous formulation, \(y_t\) is divisible, activation has no fixed cost, and every endpoint receiving positive mass must satisfy the proportional lower bound \(y_t\ge P_t/\ell\).
Thus the condition \(y_t>0\) does not introduce a fixed-charge or support-selection constraint. It is implied automatically by the linear capacity inequality. The remaining decisions are fractional transportation decisions, producing exactly the LP above.
For every fixed \(\ell\ge4\), the exact continuous mass formulation is polynomial-time solvable. The discrete NP-completeness result therefore does not extend to this formulation unless \(\mathrm{P}=\mathrm{NP}\).
⟨structured verdict parsed — rendered above⟩
The prover fully resolves the target. The proposed linear program is polynomial in the input size, and the two directions of the claimed equivalence correctly preserve all conditions in the continuous path formulation. No unsupported transfer from the discrete problem is used.
The relation \(R^+\) correctly records exactly those ordered pairs that can be the endpoints of a positive-length allowed path. Because the original formulation imposes no capacities, costs, or conservation constraints on intermediate vertices, retaining only the starting and ending types loses no relevant information.
The diagonal case is explicitly recognized: \((t,t)\in R^+\) only when the adopted path convention permits a positive-length return path. Computing reachability and storing polynomial-length witnesses is routine on a finite directed graph.
The variable \(x_{ts}\) correctly aggregates all positive-length path mass starting at \(t\) and ending at \(s\). The equality
\[ y_t+\sum_{s:(t,s)\in R^+}x_{ts}=\mu_t \]
exactly separates the prescribed zero-length mass \(y_t\) from all positive-length path mass starting at \(t\).
The formula
\[ P_s=y_s+\sum_{t:(t,s)\in R^+}x_{ts} \]
correctly includes the zero-length path at \(s\) and every positive-length path ending at \(s\). Thus the constraint \(P_s\le \ell y_s\) is represented exactly by the displayed linear inequality.
The rewrite
\[ v_ty_t+d_t(\mu_t-y_t)=d_t\mu_t+(v_t-d_t)y_t \]
is algebraically correct and introduces no nonlinear dependence on the variables.
Aggregating path masses by their ordered endpoint pairs gives nonnegative \(x_{ts}\), preserves every starting-mass equality, and reproduces each \(P_s\). The argument also preserves the original budget and bounded-power constraints.
Since the set of finite paths in a finite graph is countable and the total assigned mass is finite, the aggregate sums used here are well-defined.
Assigning \(x_{ts}\) to one stored witness path for each reachable pair preserves the required starting masses and endpoint totals. No condition in the stated problem depends on which intermediate vertices the path traverses.
The strict endpoint-support condition is verified correctly. If \(x_{ts}>0\), then \(P_s\ge x_{ts}>0\), and from \(P_s\le\ell y_s\) with \(\ell>0\), it follows that \(y_s>0\). Zero-length paths also satisfy the endpoint condition automatically whenever they have positive mass, since their mass is \(y_s\).
There are at most \(|T|^2\) variables \(x_{ts}\), in addition to \(|T|\) variables \(y_t\), and polynomially many rational constraints. Rational multiplication in constants such as \(d_t\mu_t\) produces only polynomial encoding length. Standard rational linear-program feasibility therefore gives a polynomial-time decision procedure.
The witness representation is also polynomial: at most \(|T|^2+|T|\) paths have positive mass, and reachability witnesses can be stored with polynomial length.
The proof establishes polynomial-time solvability for every fixed \(\ell\ge4\). Its stronger statement for positive rational \(\ell\) supplied as input is also supported by the same LP 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.