On the Convergence of Tâtonnement for Linear Fisher Markets (aaai25-33535)

Given a finite type set \(T\), rational masses \(\mu_t\) summing to \(1\), budget densities \(b_t>0\), valuation vectors \(v_t\in\mathbb{Q}_{\ge0}^m\), unit supply per unit population mass, initial prices \(p^0\), stepsize \(\eta\) satisfying the paper’s explicit lower-bound conditions, and accuracy \(\epsilon>0\), define \(D_t(p)=\arg\max\{v_t\cdot x:p\cdot x\le b_t,\ x\ge0\}\). Iteratively choose \(x_t^k\in D_t(p^k)\), set \(z_j^k=\sum_t\mu_t x_{tj}^k-1\), and update \(p_j^{k+1}=p_j^k+\eta z_j^k\); compute \(p^K\) and type-level demands yielding \(\lVert p^K-p^\star\rVert_2\le\epsilon\), or an \(\epsilon\)-approximate market equilibrium.

A society is given by its support: the list of \(\tau\geq1\) types with positive binary-rational masses \(\mu_t\), summing to \(1\); \(\tau\) is the support size, not the number of possible types. There are \(m\geq1\) divisible goods, each with supply \(1\). Budgets \(b_t\in\mathbb{Q}_{>0}\) are per unit mass; valuations \(v_t\in\mathbb{Q}_{\geq0}^m\) satisfy \(\lVert v_t\rVert_1=1\), and every good has positive valuation for some supported type.
Let \(B=\sum_t\mu_tb_t\), \(B_{\min}=\min_t\mu_tb_t\), \(\tilde p_j=\frac{B_{\min}}{4m}\max_t\frac{v_{tj}}{\lVert v_t\rVert_\infty}\), and \(\gamma=\min_j\tilde p_j\).
For positive prices, define \(D_t(p)=\operatorname{argmax}\{v_t\cdot x:p\cdot x\leq b_t,\ x\in\mathbb{R}_{\geq0}^m\}\). The unique equilibrium price vector \(p^\star\) admits bundles \(x_t^\star\in D_t(p^\star)\) with \(\sum_t\mu_tx_{tj}^\star=1\) for every good; write \(\rho=\min_jp_j^\star\).
Inputs include rational \(p^0\geq\tilde p\) with \(\sum_jp_j^0=B\), accuracy \(\epsilon>0\), and a constant rational stepsize promised to satisfy \(0<\eta\leq\min\{\gamma/(4m),\,2\epsilon^2\rho/[9B^2(2B/\gamma+m)^2]\}\).
At each discrete iteration choose rational \(x_t^k\in D_t(p^k)\), allowing arbitrary splitting among tied optimal goods, and update \(p_j^{k+1}=p_j^k+\eta(\sum_t\mu_tx_{tj}^k-1)\), without projection.
The computational task is to find a finite \(K\), the resulting \(p^K\), and demands \(x_t^K\in D_t(p^K)\), with \(\lVert p^K-p^\star\rVert_2\leq\epsilon\); demand choices are made by the algorithm. Let \(L\) be the total binary input length, including \(p^0,\eta,\epsilon\).

Is this trajectory-constrained computational task solvable in time polynomial in \(m,\tau,L\), or is it NP-hard?

For finite buyers, [Nan, Gao and Kroer](https://arxiv.org/html/2406.12526v2) establish geometric last-iterate convergence to a stepsize-dependent neighborhood, for every demand selection; this is not a polynomial bit-complexity guarantee.
[Orlin](https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.10171.2) gives a strongly polynomial algorithm for unrestricted linear Fisher equilibrium computation. Neither verified result establishes polynomial bit complexity for the trajectory-constrained task above.

Proven partial result: doubly exponential bit complexity

Under the standard model in which the exact rational endpoint is output as binary numerators and denominators, polynomial-time solvability is ruled out unconditionally.

I also establish a general upper bound of
$$ 2^{\,2^{O(L)}} $$
bit operations. Together with the lower bound below, this identifies the doubly exponential scale of worst-case explicit-output complexity. It does not establish $\mathrm{NP}$-hardness; that part of the requested classification remains open.

1. Aggregation and a computable lower bound on equilibrium prices

Define each type’s aggregate budget and aggregate allocation by
$$ w_t=\mu_tb_t,\qquad y_t=\mu_tx_t. $$
The substitution $y_t=\mu_tx_t$ is a bijection between the original demand problem and a finite buyer’s demand problem with valuation $v_t$ and budget $w_t$: the budget constraint becomes $p\cdot y_t\leq w_t$, and the objective is multiplied by the positive constant $\mu_t$.

Thus the society is exactly equivalent to a finite Fisher market with $\tau$ buyers, budgets $w_t$, and unit supplies. Its price update is
$$ p_j^{k+1}=p_j^k+\eta\left(\sum_ty_{tj}^k-1\right). $$

At any positive price vector, put
$$ r_t(p)=\max_j\frac{v_{tj}}{p_j}. $$
For every feasible bundle $y_t$,
$$ v_t\cdot y_t\leq r_t(p)\,p\cdot y_t\leq r_t(p)w_t. $$
Spending the entire budget on a maximizing good attains equality. Since $r_t(p)>0$, every optimal bundle exhausts its budget and purchases only maximizing goods.

At equilibrium, market clearing consequently gives
$$ \sum_jp_j^\star =\sum_tp^\star\cdot y_t^\star =\sum_tw_t =B. $$

Lemma. Every equilibrium coordinate satisfies
$$ p_j^\star\geq4\tilde p_j, \qquad\text{and hence}\qquad \rho\geq4\gamma. $$

Proof. Market clearing and nonnegativity imply $y_{tj}^\star\leq1$. Therefore
$$ r_t(p^\star)w_t =v_t\cdot y_t^\star \leq m\lVert v_t\rVert_\infty. $$
For every $j$ with $v_{tj}>0$, the definition of $r_t$ now yields
$$ p_j^\star \geq\frac{v_{tj}}{r_t(p^\star)} \geq\frac{w_t}{m}\frac{v_{tj}}{\lVert v_t\rVert_\infty} \geq\frac{B_{\min}}{m}\frac{v_{tj}}{\lVert v_t\rVert_\infty}. $$
For $v_{tj}=0$, the final inequality also holds. Maximizing over $t$ proves
$$ p_j^\star \geq\frac{B_{\min}}m \max_t\frac{v_{tj}}{\lVert v_t\rVert_\infty} =4\tilde p_j. $$
Taking the minimum over $j$ proves the second assertion. $\square$

This bound allows us to choose a stopping index without computing $p^\star$.

2. An explicit stopping index

We use the following specialization of Lemma 1 and Theorem 1 of [Nan, Gao and Kroer](https://arxiv.org/html/2406.12526v2). For a finite linear Fisher market with positive budgets, normalized nonnegative valuations, no zero valuation columns, initial prices $p^0\geq\tilde p$ summing to $B$, and
$$ 0<\eta\leq\frac{\gamma}{4m}, $$
every demand selection satisfies
$$ p_j^k\geq\tilde p_j-2m\eta>0 $$
and
$$ \lVert p^k-p^\star\rVert_2^2 \leq \left(1-\frac{4\eta\rho}{9B^2}\right)^k \lVert p^0-p^\star\rVert_2^2 + \frac{9\eta B^2}{4\rho} \left(\frac{2B}{\gamma}+m\right)^2. $$
The constants follow from their quadratic-growth modulus and excess-demand bound, using
$$ \tilde p_j-2m\eta\geq\frac{\tilde p_j}{2}, \qquad \left(1+\frac{\eta}{\tilde p_j-2m\eta}\right)B \leq\frac{3B}{2}. $$

All hypotheses hold after the aggregation in Section 1: budgets $w_t$ are positive, valuations and supplies are unchanged, every column has a positive valuation, and the initial-price and stepsize conditions are input promises.

The second stepsize promise makes the additive term at most $\epsilon^2/2$. Moreover, because both $p^0$ and $p^\star$ are nonnegative and sum to $B$,
$$ \lVert p^0-p^\star\rVert_2\leq2B. $$
Consequently,
$$ \lVert p^k-p^\star\rVert_2^2 \leq 4B^2\left(1-\frac{4\eta\rho}{9B^2}\right)^k +\frac{\epsilon^2}{2}. $$

Define the input-computable rational
$$ \delta=\frac{16\eta\gamma}{9B^2}. $$
Section 1 gives $4\eta\rho/(9B^2)\geq\delta$. The geometric factors are nonnegative: indeed, $\rho\leq B$, $\gamma\leq B/(4m)$, and therefore
$$ 0<\frac{4\eta\rho}{9B^2} \leq\frac{4\eta}{9B} \leq\frac{1}{36m^2}<1. $$
We obtain
$$ \lVert p^k-p^\star\rVert_2^2 \leq4B^2(1-\delta)^k+\frac{\epsilon^2}{2}. $$

Let $M$ be the least nonnegative integer satisfying
$$ 2^M\geq\max\left\{1,\frac{8B^2}{\epsilon^2}\right\}, $$
and choose
$$ K=\left\lceil\frac{M}{\delta}\right\rceil. $$
If $M=0$, then $4B^2\leq\epsilon^2/2$, so the displayed distance bound already suffices at $K=0$. Otherwise,
$$ (1-\delta)^K \leq e^{-\delta K} \leq e^{-M} \leq2^{-M}. $$
Thus in either case,
$$ \lVert p^K-p^\star\rVert_2^2 \leq4B^2\,2^{-M}+\frac{\epsilon^2}{2} \leq\epsilon^2. $$

The index $K$ guarantees success for every demand selection and uses only input data.

3. A general doubly exponential algorithm

Fix this deterministic demand rule: each type spends its entire budget on the smallest-index good maximizing $v_{tj}/p_j^k$.

The rule produces rational optimal demands. In aggregate form, define
$$ s_j^k=\sum_{\{t:\,t\text{ chooses }j\}}w_t. $$
Then each coordinate obeys
$$ p_j^{k+1} =p_j^k+\eta\left(\frac{s_j^k}{p_j^k}-1\right). $$
Every $s_j^k$ is a subset sum of the input aggregate budgets.

The stopping index is at most exponential

For ordinary explicit binary rational encoding, every positive input rational lies between $2^{-L}$ and $2^L$. In particular,
$$ B\leq2^L,\qquad B_{\min}\geq2^{-2L},\qquad \eta\geq2^{-L},\qquad \epsilon\geq2^{-L}. $$
Every good has a positive valuation entry, and $\lVert v_t\rVert_\infty\leq1$. Hence
$$ \gamma\geq\frac{2^{-3L}}{4m}. $$
It follows that
$$ \delta\geq\frac{4}{9m}\,2^{-6L}, \qquad M\leq4L+3. $$
The explicit input has $m,\tau=O(L)$, so
$$ K\leq2^{O(L)}. $$
The rational parameters defining $K$ have $O(L)$ bits: sums can use a common denominator obtained by multiplying input denominators, whose total encoded length is at most $L$. Thus $K$ itself can be computed in polynomial time.

Exact arithmetic grows by at most a factor of two per step

Let $H_k$ be the maximum numerator or denominator bit length among the reduced price coordinates at iteration $k$.

All aggregate budgets have a common denominator $Q$ with $O(L)$ bits. Write
$$ s_j^k=\frac{S_j^k}{Q}, \qquad \eta=\frac EF, \qquad p_j^k=\frac AD. $$
Since $0\leq s_j^k\leq B\leq2^L$, both $S_j^k$ and $Q$ have $O(L)$ bits. The update is exactly
$$ p_j^{k+1} = \frac{FQA^2-EQAD+ES_j^kD^2}{FQAD}. $$
Each displayed numerator and denominator has at most $2H_k+cL$ bits for an absolute constant $c$. Reduction of a fraction cannot increase these lengths. Therefore
$$ H_{k+1}\leq2H_k+cL, $$
and induction gives
$$ H_k\leq(H_0+cL)2^k=O(L\,2^k). $$

Optimal-good comparisons, subset sums, rational updates, and fraction reductions all take polynomial time in $L$ and $H_k$, using elementary integer arithmetic. Summing these costs through iteration $K$ gives
$$ 2^{O(K+L)} \leq2^{\,2^{O(L)}}. $$
At iteration $K$, the same rule supplies the required final demands
$$ x_{tj}^K= \begin{cases} b_t/p_j^K,&j\text{ is the chosen good for }t,\\ 0,&\text{otherwise}. \end{cases} $$
Their encoding lengths satisfy the same bound.

This proves a general explicit-output algorithm with doubly exponential running time.

4. A promised family forcing doubly exponential output

For completeness, the lower bound from the notes is proved here.

Fix $n\geq20$, and take
$$ m=\tau=2,\qquad \mu_1=\mu_2=\frac12,\qquad b_1=b_2=1, $$
$$ v_1=(1,0),\qquad v_2=(0,1). $$
Then
$$ B=1,\qquad B_{\min}=\frac12,\qquad \tilde p_1=\tilde p_2=\gamma=\frac1{16}. $$
Each demand is unique:
$$ x_1(p)=(1/p_1,0),\qquad x_2(p)=(0,1/p_2). $$
Indeed, maximizing consumption of the sole valued good exhausts the budget, leaving zero expenditure for the other good. Market clearing therefore forces
$$ p^\star=(1/2,1/2),\qquad \rho=\frac12. $$

Choose
$$ \epsilon=\frac18,\qquad \eta=2^{-n},\qquad p^0=\left(\frac34+\frac{\eta}{2}, \frac14-\frac{\eta}{2}\right). $$
These prices sum to $B$ and exceed $\tilde p$. The stepsize promise is
$$ \eta\leq\min\left\{\frac1{128},\frac1{665856}\right\}, $$
because
$$ \frac{2\epsilon^2\rho} {9B^2(2B/\gamma+m)^2} =\frac1{64\cdot9\cdot34^2} =\frac1{665856}. $$
Since $2^{20}>665856$, every stated $n$ satisfies the promise. The input length is $L=\Theta(n)$.

Positivity and existence of successful endpoints

Put $a=1/2$. Both coordinates necessarily follow
$$ q^{k+1}=q^k+\eta\left(\frac{a}{q^k}-1\right), $$
with the identity
$$ q^{k+1}-a=(q^k-a)\left(1-\frac{\eta}{q^k}\right). $$
Initially,
$$ \eta<p_2^0<a<p_1^0<1. $$
For $q^k>\eta$, the multiplier lies strictly between zero and one. Induction therefore gives
$$ a<p_1^k\leq p_1^0,\qquad p_2^0\leq p_2^k<a. $$
In particular, the trajectory remains positive and is defined forever.

Since every coordinate stays below one,
$$ |p_j^{k+1}-a| \leq(1-\eta)|p_j^k-a|. $$
Thus $p^k\longrightarrow p^\star$, and successful finite endpoints exist.

Every successful endpoint occurs late

If $\lVert p^K-p^\star\rVert_2\leq1/8$, then $p_1^K\leq5/8$. At every step,
$$ 0<p_1^k-p_1^{k+1} =\eta\left(1-\frac{a}{p_1^k}\right)<\eta. $$
The initial point is outside the requested neighborhood, so $K>0$. Summing gives
$$ K\eta>p_1^0-p_1^K \geq\frac18+\frac{\eta}{2}. $$
Consequently,
$$ K>2^{n-3}+\frac12, \qquad\text{in particular}\qquad K\geq2^{n-3}. $$

5. Denominators grow without cancellation

Scale the first coordinate by $\eta$:
$$ y_k=\frac{p_1^k}{\eta}, \qquad C=\frac{a}{\eta}=2^{n-1}. $$
Then
$$ y_{k+1}=y_k-1+\frac{C}{y_k}, \qquad y_0=\frac{3\cdot2^{n-1}+1}{2}. $$

We prove that the reduced expression $y_k=A_k/D_k$ has $A_k$ odd, $D_k$ even, and satisfies
$$ A_{k+1}=A_k^2-A_kD_k+CD_k^2, \qquad D_{k+1}=A_kD_k. $$
The assertions hold initially. Suppose they hold at iteration $k$, and write
$$ N=A_k^2-A_kD_k+CD_k^2. $$
The integer $N$ is odd. Moreover,
$$ \gcd(N,D_k)=\gcd(A_k^2,D_k)=1, $$
and
$$ \gcd(N,A_k) =\gcd(CD_k^2,A_k) =\gcd(C,A_k) =1. $$
The second calculation uses $\gcd(A_k,D_k)=1$; the last equality uses that $C$ is a power of two and $A_k$ is odd. Hence $\gcd(N,A_kD_k)=1$, so no cancellation occurs. The new numerator is positive because $y_{k+1}>0$. This completes the induction.

Since $p_1^k>a$,
$$ \frac{A_k}{D_k}>C. $$
Therefore
$$ D_{k+1}=A_kD_k>CD_k^2\geq D_k^2. $$
Starting from $D_0=2$, induction yields
$$ D_k\geq2^{\,2^k}. $$

Returning to the price coordinate,
$$ p_1^k=\frac{A_k}{2^nD_k}. $$
This fraction is reduced because $A_k$ is odd and coprime to $D_k$. Its denominator therefore requires at least $2^k+1$ binary digits.

Every successful endpoint has $K\geq2^{n-3}$, so writing its first price coordinate requires at least
$$ 2^K\geq2^{\,2^{n-3}} $$
bits.

Allowing an unreduced fraction does not help. If $A/Q$ is reduced and $A/Q=P/R$ with $R>0$, then $AR=PQ$ and coprimality implies $Q\mid R$. Thus an alternative denominator cannot be smaller.

Because $L=\Theta(n)$, every successful explicit output on this family has length
$$ 2^{\,2^{\Omega(L)}}. $$
This excludes polynomial running time even for algorithms that skip intermediate iterations internally. Unique demands also exclude any escape through tie splitting.

6. What remains unresolved

The proved bounds are:

• Some promised inputs with $m=\tau=2$ require $2^{\,2^{\Omega(L)}}$ explicit output bits.
• Every promised input admits an algorithm using $2^{\,2^{O(L)}}$ bit operations.

These bounds settle the polynomial-time alternative negatively under exact explicit rational output. They do not provide an $\mathrm{NP}$-hardness reduction. Establishing that classification requires a specified reduction notion for this search task and a valid reduction under that notion.

⟨structured verdict parsed — rendered above⟩

Verification report

Assessment: correct partial result. Under explicit binary numerator-and-denominator output, the argument establishes both a doubly exponential worst-case output-length lower bound and a doubly exponential running-time upper bound. No mathematical error or substantive proof gap was found in these claims.

The requested $\mathrm{NP}$-hardness classification remains unresolved, as the prover explicitly acknowledges. Failure of polynomial-time solvability due to output length does not itself establish $\mathrm{NP}$-hardness.

1. Aggregation and equilibrium-price bound

The substitution
$$ w_t=\mu_tb_t,\qquad y_t=\mu_tx_t $$
is valid because every supported mass is positive. It bijectively maps feasible bundles to bundles with budget $w_t$, preserves optimality through positive scaling of the objective, and converts aggregate market clearing and price updates exactly as stated.

At positive prices, $r_t(p)>0$ because each valuation vector has norm $1$. The displayed utility bound is correct. Its equality conditions justify both full budget expenditure and purchasing only maximizing goods. Consequently, equilibrium market clearing implies
$$ \sum_jp_j^\star=B. $$

The price-bound lemma is also correct. Each aggregate equilibrium allocation satisfies $y_{tj}^\star\leq1$, so
$$ r_t(p^\star)w_t\leq m\lVert v_t\rVert_\infty. $$
The subsequent inequalities have the correct directions. Zero valuation entries cause no problem, and maximizing over supported types establishes
$$ p_j^\star\geq4\tilde p_j,\qquad \rho\geq4\gamma. $$
Every good has a positive supported valuation, so $\gamma>0$.

Finding: verified.

2. Cited convergence theorem and stopping index

The cited source gives the trajectory lower bound, excess-demand bound, coordinate upper bound, and convergence estimate used here. Its demand choices are arbitrary, and its strict stepsize hypothesis is satisfied by the stronger input promise. The initial condition $\sum_jp_j^0=B$ also supplies the needed initial coordinate upper bounds. See [Nan, Gao and Kroer, Lemmas 1 and 3 and Theorem 1](https://arxiv.org/html/2406.12526v2#S4).

The stated specialization has the correct constants. The bound on coordinate upper prices gives a quadratic-growth modulus at least $2\rho/(9B^2)$, while the excess-demand bound is at most $2B/\gamma+m$. These yield precisely the displayed contraction coefficient and additive term.

The second stepsize promise makes that additive term at most $\epsilon^2/2$. The initial-distance bound $2B$ is valid, although loose.

The checks that the geometric factors are positive are correct:
$$ \gamma\leq\frac{B}{4m},\qquad \eta\leq\frac{B}{16m^2},\qquad \frac{4\eta\rho}{9B^2}\leq\frac1{36m^2}<1. $$
The computable $\delta$ is positive and no larger than the displayed contraction coefficient.

Both stopping-index cases are handled correctly:

• If $M=0$, the initial-distance bound already suffices.
• If $M>0$, the estimates involving $e^{-\delta K}$ and $2^{-M}$ give the required squared-distance bound.

Neither the stopping index nor the stopping decision requires knowing $p^\star$.

Finding: verified.

3. General exact-arithmetic upper bound

The deterministic demand rule is well-defined and rational. A maximizing good has positive valuation, and spending the full budget there gives an optimal bundle.

The subset-sum representation and coordinate recurrence are exact. The binary-size estimates are valid under the stated explicit rational encoding. In particular, the estimates for $B_{\min}$ and $\gamma$ are conservative, and they imply
$$ \delta\geq\frac4{9m}2^{-6L},\qquad M\leq4L+3,\qquad K\leq2^{O(L)}. $$
Using a common denominator formed from input denominators gives the claimed linear bit-length bounds for the rational parameters and aggregate-budget subset sums.

The update formula was checked:
$$ p_j^{k+1} = \frac{FQA^2-EQAD+ES_j^kD^2}{FQAD}. $$
Each term has at most $2H_k+O(L)$ bits, giving the claimed recurrence and its solution. Fraction reduction cannot increase numerator or denominator lengths.

Comparisons, exact updates, and reductions have polynomial cost in the current integer lengths. Summing these costs through the exponential stopping index gives
$$ 2^{\,2^{O(L)}}. $$
The final demands are optimal and have encoding lengths within the same bound.

Finding: verified.

4. Promised lower-bound family

All input conditions are satisfied:

• The two masses are positive and sum to $1$.
• Budgets are positive and valuations are normalized.
• Both goods have positive supported valuation.
• The initial prices sum to $B$ and exceed their required lower bounds.
• The stepsize promise holds for every $n\geq20$.

The numerical calculation
$$ \frac{2\epsilon^2\rho}{9B^2(2B/\gamma+m)^2} =\frac1{665856} $$
is correct, and $2^{20}>665856$.

Demand uniqueness is correctly justified. Positive prices and budget exhaustion prevent either buyer from purchasing any amount of the unvalued good. Thus there is no alternative trajectory through demand selection.

The coordinate recurrence and its error identity are correct. The induction keeps both coordinates positive, below $1$, and strictly on their original sides of $1/2$. The contraction estimate therefore establishes convergence and existence of successful finite endpoints.

For every successful endpoint, the Euclidean-distance condition implies $p_1^K\leq5/8$. Each first-coordinate decrease is positive and strictly less than $\eta$. Summing yields
$$ K>2^{n-3}+\frac12, $$
which implies the weaker bound subsequently used.

Finding: verified, including the quantifier over every successful endpoint.

5. Denominator growth and output lower bound

The scaling, initial fraction, and recurrence are correct:
$$ y_{k+1}=y_k-1+\frac{C}{y_k}, \qquad C=2^{n-1}. $$

The no-cancellation induction checks out. Assuming the current fraction is reduced with odd numerator and even denominator:

• The new numerator is odd.
• It is coprime to the old denominator.
• It is coprime to the old numerator because $C$ is a power of two.

These facts establish coprimality with their product. Positivity follows from the already-established positive trajectory.

Since $y_k>C$, the denominator recurrence gives
$$ D_{k+1}>CD_k^2\geq D_k^2. $$
Starting from $D_0=2$, the stated bound follows. Rescaling to the price introduces no cancellation because the numerator is odd.

Combining denominator growth with the necessary stopping-index lower bound establishes the claimed doubly exponential number of explicit output bits. The divisibility argument for unreduced fractions is correct. It also correctly excludes algorithms that internally skip iterations: the required endpoint itself remains too large to write.

Finding: verified.

6. Scope and actionable feedback

The exact explicit-output convention is stated clearly and is the natural interpretation of binary rational output. The lower bound applies within that convention; no conclusion about succinct arithmetic-circuit representations is established or claimed.

The output contains genuine progress throughout. Its upper and lower bounds stand as written. There is no mathematical repair needed for those results.

To complete the requested hardness classification, the prover must specify a reduction notion for this trajectory-constrained search task and establish $\mathrm{NP}$-hardness under that notion. The current output supplies neither and accurately identifies that remaining work. The alternatives in the question should not be treated as logically exhaustive merely because polynomial-time solvability has been excluded.

⟨structured verdict parsed — rendered above⟩