Answer: —
Theorem 13 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateSC-PIZZA-SHARING is FIXP-hard even when every mass distribution consists of at most six pieces that can be unit-squares or right-angled triangles, and they have overlap 3. ETR-hardness. We can also show that deciding whether there is an exact SC-PIZZA-SHARING solution with 𝑛−2 turns exists is ETR-hard. To show this, we will use a result of (Deligkas et al. 2021), where it was shown that deciding whether there exists an exact CONSENSUS-HALVING solu- tion with 𝑛 agents and 𝑛−1 cuts is ETR-hard.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite catalogue \(T\), a rational population distribution \(\boldsymbol{\mu}\) over \(T\), and for each populated type \(t\) a normalized valuation \(v_t\) consisting of at most six unit squares or right-angled triangles with overlap at most \(3\), output a \(y\)-monotone, non-crossing, wraparound square-cut path \(P\) with at most \(\tau-1\) turns, where \(\tau=|\operatorname{supp}(\boldsymbol{\mu})|\), such that \(v_t(R^+(P))=v_t(R^-(P))\) for every populated type \(t\).
Definitions. Work on \([0,1]^2\) with its left and right boundaries identified. The input is a finite catalogue \(T\), a rational distribution \(\boldsymbol{\mu}\) on \(T\), and normalized valuations \(v_t\) for each \(t\in\operatorname{supp}(\boldsymbol{\mu})\). Each \(v_t\) consists of at most six unit squares or right-angled triangles, and at every point at most three populated types have positive valuation density.
A square-cut path is a non-crossing path of horizontal and vertical segments on this wraparound domain; it is \(y\)-monotone if it never moves downward. It partitions the domain into regions \(R^+(P)\) and \(R^-(P)\). Let \(\tau=|\operatorname{supp}(\boldsymbol{\mu})|\).
Target. Is finding a \(y\)-monotone square-cut path \(P\) with at most \(\tau-1\) turns such that \(v_t(R^+(P))=v_t(R^-(P))\) for every \(t\in\operatorname{supp}(\boldsymbol{\mu})\) in \(\mathrm{P}\), or is it \(\mathrm{NP}\)-hard?
Nearest known results. For the finite-agent exact square-cut problem, finding such a path is \(\mathrm{FIXP}\)-hard even when every valuation has at most six square-or-triangle pieces and overlap at most \(3\). Exact square-cut pizza sharing for weighted polygons with holes lies in \(\mathrm{BU}\).
Complexity classes require finite input strings. I therefore use the standard encoding from exact square-cut pizza sharing: polygon vertices, piece densities, and all other numerical data are rational numbers encoded in binary.
Without an encoding for the coordinates and densities of the valuation pieces, membership in \( \mathrm{P} \) and hardness are formally undefined.
Let \( \mathrm{ExactSC}(n) \) denote the problem of finding a \(y\)-monotone square-cut path with at most \(n-1\) turns that simultaneously bisects \(n\) mass distributions.
The known theorem states that \( \mathrm{ExactSC}(n) \) is \( \mathrm{FIXP} \)-hard even when every mass distribution has at most six unit-square or right-angled-triangle pieces and the pointwise overlap is at most \(3\). The formulation uses the same horizontally wraparound domain and the same \(y\)-monotone path condition as the present problem. It also belongs to \( \mathrm{BU} \) for weighted polygons with holes. See [Deligkas, Fearnley, and Melissourgos](https://arxiv.org/abs/2012.14236).
Suppose a mass distribution \(w_i\) occurring in the known hardness theorem has total mass
\(M_i=w_i([0,1]^2)>0\).
Define the normalized valuation
\(\bar w_i(A)=w_i(A)/M_i\).
Then, for every square-cut path \(P\),
\(w_i(R^+(P))=w_i(R^-(P))\)
if and only if
\(\bar w_i(R^+(P))=\bar w_i(R^-(P))\).
Thus normalization does not change the set of feasible paths. Multiplication by the positive constant \(1/M_i\) also preserves:
Under the rational weighted-polygon encoding, \(M_i\) is rational and has polynomial encoding length: the area of a rational square or rational right-angled triangle is rational, and there are at most six pieces. Hence normalization is polynomial-time computable.
Take an instance of \( \mathrm{ExactSC}(n) \) with normalized mass distributions \(w_1,\ldots,w_n\). Construct
\(T=\{t_1,\ldots,t_n\}\),
set
\(\boldsymbol{\mu}(t_i)=1/n\)
for every \(i\), and define
\(v_{t_i}=w_i\).
This construction is polynomial-time and produces a rational distribution. Moreover,
\(\operatorname{supp}(\boldsymbol{\mu})=T\)
and hence
\(\tau=|\operatorname{supp}(\boldsymbol{\mu})|=n\).
Consequently, the permitted number of turns in the population instance is
\(\tau-1=n-1\),
exactly the turn budget of the original instance.
For every path \(P\) and every \(i\),
\(v_{t_i}(R^+(P))=v_{t_i}(R^-(P))\)
if and only if
\(w_i(R^+(P))=w_i(R^-(P))\).
Therefore the original and constructed instances have exactly the same feasible paths. The solution-decoding map is the identity. The six-piece and overlap-\(3\) restrictions are unchanged.
This proves a solution-preserving polynomial-time reduction from finite-agent exact square-cut to the population problem.
Conversely, given a population instance, enumerate the valuations
\(\{v_t:t\in\operatorname{supp}(\boldsymbol{\mu})\}\)
as \(\tau\) finite-agent mass distributions and discard \(\boldsymbol{\mu}\). The resulting finite-agent instance has the same turn budget and exactly the same feasible paths.
Thus the population distribution plays no role: under type-by-type bisection, the population problem is polynomial-time search-equivalent to finite-agent exact square-cut.
Under the standard rational weighted-polygon encoding, the target problem is therefore:
In particular, a polynomial-time exact-search algorithm would yield polynomial-time algorithms for every problem in \( \mathrm{FIXP} \) under the corresponding real-valued search reductions.
The target is a total, potentially irrational-output search problem. Its appropriate complexity notions are \( \mathrm{FIXP} \) and \( \mathrm{BU} \), rather than the decision classes \( \mathrm{P} \) and \( \mathrm{NP} \). The distinction is substantive; \( \mathrm{FIXP} \)-hardness does not formally imply classical \( \mathrm{NP} \)-hardness. See the framework of [Etessami and Yannakakis](https://doi.org/10.1137/080720826).
Indeed, if the question is interpreted as the decision problem
“does a path with at most \(\tau-1\) turns exist?”,
then the answer is always yes by the square-cut existence theorem. That decision problem is therefore trivial. The computational difficulty is finding an exact path, whose coordinates may be irrational.
Hence the proposed dichotomy is not valid as stated. What follows rigorously is \( \mathrm{FIXP} \)-hardness and \( \mathrm{BU} \)-membership, not classical \( \mathrm{NP} \)-hardness.
⟨structured verdict parsed — rendered above⟩
The output establishes a correct polynomial-time, solution-preserving equivalence between the population formulation and the corresponding finite-agent exact square-cut problem, conditional on the stated rational weighted-polygon encoding. It therefore transfers the supplied \( \mathrm{FIXP} \)-hardness result and the supplied \( \mathrm{BU} \)-membership result.
It does not establish either alternative requested literally by the target: it gives neither a polynomial-time exact-search algorithm nor classical \( \mathrm{NP} \)-hardness. Its conclusion that the stated dichotomy is underspecified is reasonable, but the original classification remains unresolved.
The observation that complexity classifications require a finite input encoding is correct. Rational binary encoding of vertices and densities is a suitable conditional interpretation.
There is, however, a second encoding issue that is not fully formalized: because exact solutions can have irrational coordinates, “polynomial-time exact-search algorithm” requires an output representation and computational model. Rational input encoding alone does not define what it means for a Turing machine to output an exact irrational path. The references to \( \mathrm{FIXP} \) and \( \mathrm{BU} \) implicitly select real-valued search frameworks, but this should be stated explicitly when comparing the problem with \( \mathrm{P} \) or \( \mathrm{NP} \).
The substantive theorem invoked is consistent with the supplied nearest-known result. The cited paper states hardness for at most six square-or-right-triangle pieces with overlap at most \(3\), and its construction produces the required monotone square paths. The published formulation defines square-pizza sharing using at most \(n-1\) turns and a \(y\)-monotone path. [Definition 3 and Theorem 19](https://repository.essex.ac.uk/40655/1/pizza_sharing.pdf)
The notation \( \mathrm{ExactSC}(n) \) is slightly misleading. If \(n\) were fixed, the statement “\( \mathrm{ExactSC}(n) \) is \( \mathrm{FIXP} \)-hard” would not be the usual theorem. The theorem concerns the problem family in which \(n\) varies with the input. The subsequent reduction clearly uses that intended meaning, so this is an expositional defect rather than a substantive error.
This part is correct under the adopted weighted-polygon encoding.
For \(M_i>0\), division by \(M_i\) preserves the bisection equation because both sides are multiplied by the same positive number. It also preserves the geometric pieces and the positive-density overlap pattern.
With rational vertices and rational constant densities, each piece has rational mass. Since there are at most six pieces, summing their masses and rescaling their densities has polynomial bit complexity. The write-up should explicitly note that the distributions in the hardness instances have positive total mass, although that is standard for mass distributions and is implicit in their normalization.
The construction is correct:
Thus the identity solution map is valid.
Discarding \( \boldsymbol{\mu} \) and retaining one finite-agent valuation for every type in its support also preserves the feasible paths and turn budget.
This is polynomial-time provided the rational distribution and catalogue are explicitly represented, so that zero probabilities can be recognized and the support enumerated. That is compatible with the prover’s encoding assumption.
The conclusion that \( \boldsymbol{\mu} \) is irrelevant to feasibility is correct because the target imposes separate bisection constraints for every populated type; it never aggregates those constraints using the population probabilities.
The transfer of \( \mathrm{FIXP} \)-hardness is correct under the same reduction notion as the known finite-agent theorem.
The claimed \( \mathrm{BU} \)-membership follows from the nearest-known result supplied in the task because the permitted squares and triangles form a subclass of weighted polygons with holes. This is an application of the supplied premise rather than something proved independently in the output.
The statement about a polynomial-time exact-search algorithm solving every \( \mathrm{FIXP} \) problem is valid only after fixing a compatible exact-output model and the reduction notion. The phrase “under the corresponding real-valued search reductions” acknowledges this, but it remains insufficiently formal for a literal \( \mathrm{P} \)-classification.
It is correct that \( \mathrm{FIXP} \)-hardness does not, merely by definition, imply classical decision-problem \( \mathrm{NP} \)-hardness. These are different kinds of complexity assertions.
It is also true for the stated absolutely continuous valuations that the unrestricted existence question with the guaranteed \( \tau-1 \) turn budget is always affirmative: the relevant existence theorem gives a \(y\)-monotone horizontal-vertical path with at most \(n-1\) turns for \(n\) absolutely continuous measures. [Theorem 24](https://repository.essex.ac.uk/40655/1/pizza_sharing.pdf)
Nevertheless, the prover merely names the “square-cut existence theorem” without stating its hypotheses or verifying that piecewise-uniform square-and-triangle valuations are absolutely continuous. That omission leaves the claimed triviality of the decision interpretation insufficiently justified as written.
Finally, showing that the currently invoked hardness result does not imply classical \( \mathrm{NP} \)-hardness does not prove that the search problem is not \( \mathrm{NP} \)-hard under some separately defined search reduction. The defensible conclusion is that the proposed dichotomy is underspecified and not settled by the argument—not that one of its alternatives has been excluded.
The central equivalence reduction is sound and directly useful. It shows that introducing a rational population distribution does not change the exact type-by-type square-cut search problem. Consequently, the finite-agent \( \mathrm{FIXP} \)-hardness transfers without loss of the geometric restrictions.
To make the final classification verifiable, the task must specify:
After that clarification, settling the requested alternative would still require either a polynomial-time exact-search algorithm or an appropriate \( \mathrm{NP} \)-hardness reduction; neither is present here.
⟨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.