Answer: NP-hard, even for $\tau=1$ and $\epsilon=0$; deciding $D_0\le3$ is already NP-hard.
Theorem 1 — class: other
PDF text-layer excerpt — equations and symbol order may be approximateFor all G, RPDim(G) = RPDim(G+) = SgnRnk(M(G+)) −1. To show this, we first constructively show that any RP realization in d di- mensions implies a sign-rank realization with rank d + 1. Next, we argue that a sign-rank realization of M(G+) with rank r implies a weak RP realization in r −1 dimensions.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a fixed experiment protocol, a finite support of revealed-preference graph types \(G_t\) on its observation set, rational masses \(\mu_t\) summing to one, and rational \(0\le\epsilon<1\), determine the least integer \(d\ge1\) such that \(\sum_{t:\operatorname{RPDim}(G_t)\le d}\mu_t\ge1-\epsilon\).
An experiment protocol specifies a common labeled observation set \(V=\{1,\ldots,m\}\), with \(m\ge1\) part of the input. Types are loopless directed graphs on \(V\), supplied as adjacency matrices; cycles are allowed. Realizations may differ independently across types, with no prescribed numerical prices or bundles.
A society is given by its support: the list of the \(\tau\) types \(G_t\) with positive mass, each mass \(\mu_t\) a binary rational, with \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types. Let \(L\) be the total input bit length, including the binary rational \(0\le\epsilon<1\); state running times in \(m,\tau,L\).
An RP realization of \(G=(V,E)\) in dimension \(d\ge1\) consists of real vectors \(p_i\in\mathbb R_{\ge0}^d\setminus\{0\}\) and \(x_i\in\mathbb R_{\ge0}^d\). For distinct \(i,j\), require \(\langle p_i,x_i-x_j\rangle>0\) when \((i,j)\in E\), and \(\langle p_i,x_i-x_j\rangle<0\) otherwise; off-diagonal expenditure ties are excluded. Define \(\operatorname{RPDim}(G)\) as the least such positive integer dimension.
Define \(D_\epsilon=\min\{d\in\mathbb Z_{\ge1}:\sum_{t:\operatorname{RPDim}(G_t)\le d}\mu_t\ge1-\epsilon\}\).
Is computing \(D_\epsilon\) solvable in polynomial time in \(m,\tau,L\), or is it NP-hard?
For a single graph, the discrete characterization is \(\operatorname{RPDim}(G)=\operatorname{RPDim}(G^+)=\operatorname{signrank}(M(G^+))-1\): \(G^+\) adds vertices \(s,t\) and exactly the new edges \((s,v),(v,t),(s,t)\) for \(v\in V\); \(M(H)\) has zero diagonal, positive signs on edges, and negative signs elsewhere. Sign rank is the minimum rank of a real matrix with those prescribed signs. [Discrete characterization](https://arxiv.org/pdf/1807.10878).
Computing RP dimension was explicitly left open. [Discrete complexity discussion](https://arxiv.org/pdf/1807.10878). Deciding sign rank at most \(3\) for arbitrary matrices with only positive and negative signs is NP-hard. [Sign-rank hardness](https://arxiv.org/pdf/1503.04486).
No complexity classification for this distributional quantile problem was located.
Computing $D_\epsilon$ is NP-hard. More precisely, deciding whether $D_\epsilon\le 3$ is NP-hard even when $\tau=1$, $\mu_1=1$, and $\epsilon=0$.
The proof constructs an RP graph from a planar point–line realizability instance. Duplicated point vertices allow us to extract a planar realization from any three-dimensional RP realization. Additional vertices and carefully chosen signs make the converse hold as well.
A simple pseudoline arrangement consists of $n$ pseudolines such that every pair crosses exactly once and no three meet. Each pseudoline has a designated positive and negative side. Every two-dimensional cell therefore has a sign vector in $\{-,+\}^n$.
We use two known results:
Let $P$ be a source arrangement. Enumerate its cell sign vectors as
$$
S=\{\sigma^1,\ldots,\sigma^N\}\subseteq\{-,+\}^n,
\qquad
N=1+\frac{n(n+1)}2.
$$
These vectors can be obtained in polynomial time from the subdivision described by a wiring diagram: adjacent cells differ in the coordinate of the wire separating them.
Call $S$ planarly realizable if there are nonconstant affine functions
$$
f_i(y)=b_i-a_i\cdot y,
\qquad
a_i\in\mathbb R^2\setminus\{0\},
$$
and points $y_1,\ldots,y_N\in\mathbb R^2$ such that
$$
\operatorname{sign}(f_i(y_j))=\sigma_i^j
\qquad
\text{for every }i,j.
$$
Then
$$
P\text{ is stretchable}
\quad\Longleftrightarrow\quad
S\text{ is planarly realizable}.
$$
The forward implication follows by taking representative points in the cells of a straight-line realization.
For the reverse implication, an arrangement of $n$ affine lines has at most $N$ regions. Indeed, its $k$th line intersects the previous lines in at most $k-1$ distinct points and therefore creates at most $k$ new regions. Equality requires distinct lines, no parallel pair, and no triple intersection.
Distinct realized sign vectors lie in distinct regions: the set realizing any fixed strict sign vector is an intersection of open halfplanes and is consequently convex. Thus realizing all $N$ vectors forces exactly $N$ regions and a simple line arrangement whose complete region-sign set is $S$. The reconstruction result above applies to two simple arrangements, proving stretchability.
We also obtain the following useful data from $P$. For each coordinate $i$, choose two cells adjacent across a segment of pseudoline $i$. Their vectors, denoted
$$
\sigma^{u_i},\sigma^{v_i},
$$
differ exactly in coordinate $i$. For $k\ne i$, define their common sign by
$$
\alpha_{ki}=\sigma_k^{u_i}=\sigma_k^{v_i}.
$$
The reduction below uses only $S$ and these adjacent pairs.
Construct a loopless directed graph $G$ with vertices
$$
r_1,\ldots,r_n,\quad o,\quad
c_1^-,\ldots,c_N^-,\quad c_1^+,\ldots,c_N^+.
$$
Thus its number of vertices is
$$
m=n+2N+1=n^2+2n+3.
$$
Assign distinct auxiliary heights
$$
h(r_i)=\frac{i}{n+1},
\qquad h(o)=0,
\qquad h(c_j^-)=-j,
\qquad h(c_j^+)=j+1.
$$
These heights specify graph edges; they are not prescribed realization data.
Define every off-diagonal edge as follows.
$$ (w,z)\in E(G) \quad\Longleftrightarrow\quad h(w)>h(z). $$
$$ (r_i,c_j^-),(r_i,c_j^+)\in E(G) \quad\Longleftrightarrow\quad \sigma_i^j=+. $$
$$ (r_i,o)\in E(G) \quad\Longleftrightarrow\quad \sigma_i^1=+. $$
$$ (r_i,r_k)\in E(G) \quad\Longleftrightarrow\quad \alpha_{ik}=+. $$
These rules specify every ordered pair of distinct vertices.
We will prove
$$
S\text{ is planarly realizable}
\quad\Longleftrightarrow\quad
\operatorname{RPDim}(G)\le 3.
$$
Assume $S$ has a planar realization by functions $f_i(y)=b_i-a_i\cdot y$ and points $y_j$.
For each $i$, the values of $f_i$ at $y_{u_i}$ and $y_{v_i}$ have opposite signs. Hence their segment contains a point $q_i$ satisfying
$$
f_i(q_i)=0.
$$
For $k\ne i$, the values of $f_k$ at both endpoints have sign $\alpha_{ki}$. An affine function at a point of the segment is a convex combination of its endpoint values. Therefore
$$
\operatorname{sign}(f_k(q_i))=\alpha_{ki}.
$$
In particular, $q_i$ lies on none of the other lines.
Assign preliminary bundles in $\mathbb R^3$:
$$
x_{r_i}=(q_i,h(r_i)),
\qquad
x_o=(y_1,0),
\qquad
x_{c_j^\pm}=(y_j,h(c_j^\pm)).
$$
Write $Y_w\in\mathbb R^2$ for the first two coordinates of $x_w$.
For every $i$ and every $w\ne r_i$, the value $f_i(Y_w)$ is nonzero. Its sign is exactly the sign prescribed for the ordered pair $(r_i,w)$:
Choose a positive real number $\delta$ satisfying
$$
0<\delta<
\min_{\substack{1\le i\le n\\w\ne r_i}}
\frac{|f_i(Y_w)|}{1+|h(r_i)-h(w)|}.
$$
The minimum is positive because it ranges over finitely many strictly positive quantities.
Set preliminary prices
$$
p_{r_i}=(a_i,\delta),
\qquad
p_o=p_{c_j^\pm}=(0,0,1).
$$
Since $a_i\cdot q_i=b_i$, for $w\ne r_i$ we have
$$
\begin{aligned}
p_{r_i}\cdot(x_{r_i}-x_w)
&=a_i\cdot(q_i-Y_w)+\delta(h(r_i)-h(w))\\
&=f_i(Y_w)+\delta(h(r_i)-h(w)).
\end{aligned}
$$
Our choice of $\delta$ makes the perturbation strictly smaller in absolute value than $|f_i(Y_w)|$. Thus this expenditure difference has precisely the required sign.
For $w$ equal to $o$ or a point vertex,
$$
p_w\cdot(x_w-x_z)=h(w)-h(z).
$$
The heights are distinct, so these differences are nonzero and have the prescribed signs. All off-diagonal comparisons are therefore satisfied.
The preliminary prices may have negative first or second coordinates. Every price, however, has a strictly positive third coordinate.
Choose $K>0$ large enough that, for every preliminary price $p$,
$$
p_1+Kp_3>0,
\qquad
p_2+Kp_3>0.
$$
Define
$$
T=
\begin{pmatrix}
1&0&K\\
0&1&K\\
0&0&1
\end{pmatrix},
\qquad
\widehat p_w=Tp_w,
\qquad
\widehat x_w=T^{-T}x_w.
$$
Every coordinate of every $\widehat p_w$ is positive. Moreover,
$$
\widehat p_w\cdot(\widehat x_w-\widehat x_z)
=p_w\cdot(x_w-x_z).
$$
Finally, choose a common vector $v\in\mathbb R^3$ large enough coordinatewise that
$$
\widetilde x_w=\widehat x_w+v\in\mathbb R_{\ge0}^3
$$
for every vertex $w$. Translation does not change bundle differences. Hence the pairs $(\widehat p_w,\widetilde x_w)$ satisfy all requirements of an RP realization.
This proves
$$
S\text{ planarly realizable}
\quad\Longrightarrow\quad
\operatorname{RPDim}(G)\le3.
$$
The numerical choices above establish existence only. The reduction outputs just the graph’s adjacency matrix.
Conversely, suppose $G$ has an RP realization in dimension at most $3$. Append zero coordinates if necessary, obtaining vectors in $\mathbb R^3$.
For every vertex $w$, define the affine function
$$
F_w(x)=p_w\cdot(x_w-x).
$$
Because $p_o\ne0$, the set
$$
H=\{x\in\mathbb R^3:F_o(x)=0\}
$$
is an affine plane.
For every $j$, the graph construction gives
$$
(o,c_j^-)\in E(G),
\qquad
(o,c_j^+)\notin E(G).
$$
Therefore
$$
F_o(x_{c_j^-})>0,
\qquad
F_o(x_{c_j^+})<0.
$$
Their segment meets $H$ at a point $z_j$ strictly between its endpoints.
For every $i$, the two ordered pairs $(r_i,c_j^-)$ and $(r_i,c_j^+)$ have the same prescribed sign $\sigma_i^j$. Thus
$$
F_{r_i}(x_{c_j^-})
\quad\text{and}\quad
F_{r_i}(x_{c_j^+})
$$
both have sign $\sigma_i^j$. Since $F_{r_i}$ is affine, its value at $z_j$ is a convex combination of these two values. Consequently,
$$
\operatorname{sign}(F_{r_i}(z_j))=\sigma_i^j.
$$
Each coordinate $i$ takes both signs among the vectors in $S$, as witnessed by the chosen adjacent pair. Hence $F_{r_i}|_H$ takes both positive and negative values and is nonconstant.
Identify $H$ with $\mathbb R^2$ by any affine coordinate system. The functions $F_{r_i}|_H$ and points $z_j$ give a planar realization of $S$. This proves the reverse implication:
$$
\operatorname{RPDim}(G)\le3
\quad\Longrightarrow\quad
S\text{ planarly realizable}.
$$
Combining both directions with Section 1,
$$
P\text{ is stretchable}
\quad\Longleftrightarrow\quad
\operatorname{RPDim}(G)\le3.
$$
The source has $N=O(n^2)$ cell sign vectors, and the graph has $m=O(n^2)$ vertices.
The vectors and adjacent pairs can be extracted in polynomial time from the source diagram. Alternatively, once $S$ is listed, comparing all pairs of its vectors finds the required adjacent pairs using $O(nN^2)$ sign comparisons. Constructing the adjacency matrix then uses $O(m^2)$ comparisons of signs or indices. A conservative bit-operation bound for these latter steps is
$$
O\!\left((nN^2+m^2)\log(n+N+1)\right),
$$
which is polynomial in the source size. The output adjacency matrix has $m^2$ entries.
Now label the graph vertices by $\{1,\ldots,m\}$ and construct the society
$$
\tau=1,\qquad G_1=G,\qquad \mu_1=1,\qquad\epsilon=0.
$$
These masses and tolerance satisfy all input requirements, and
$$
D_0=\operatorname{RPDim}(G).
$$
Thus
$$
P\text{ is stretchable}
\quad\Longleftrightarrow\quad
D_0\le3.
$$
This is a polynomial-time many-one reduction to the quantile threshold problem. An algorithm computing $D_\epsilon$ would decide that threshold by computing its output and comparing it with $3$.
Therefore computing $D_\epsilon$ is NP-hard, and a running time polynomial in $m,\tau,L$ would imply $\mathsf P=\mathsf{NP}$.
For completeness, the quantile always exists. Every graph on $m$ vertices has an RP realization in dimension $m$: take $x_i=e_i$ and set
$$
(p_i)_j=
\begin{cases}
1,&j=i,\\
0,&(i,j)\in E,\\
2,&j\ne i\text{ and }(i,j)\notin E.
\end{cases}
$$
Then, for $i\ne j$,
$$
p_i\cdot(x_i-x_j)=1-(p_i)_j,
$$
which is $1$ on edges and $-1$ on nonedges. Appending zero coordinates preserves realizability. Consequently,
$$
1\le D_\epsilon\le m.
$$
In particular, $m=1$ is trivial; the hardness concerns variable $m$.
The support size introduces only polynomial aggregation work. Given an oracle deciding $\operatorname{RPDim}(G)\le d$, one threshold evaluation for $D_\epsilon$ uses $\tau$ oracle calls followed by an exact mass comparison. Binary search uses at most
$$
\tau\lceil\log_2m\rceil
$$
oracle calls.
To justify the arithmetic bound, write the masses and tolerance with integer denominators and multiply all comparisons by their denominator product $Q$. Its bit length is $O(L)$. Schoolbook integer arithmetic gives $O(\tau L^2)$ preprocessing and $O(\tau L)$ per mass comparison. Including graph handling, the additional work is bounded by
$$
O\!\left(\tau m^2+\tau L^2+\tau L\log(m+1)\right).
$$
The hardness proved above already holds with singleton support, so it does not depend on this aggregation step.
⟨structured verdict parsed — rendered above⟩
Verdict: proved. The reduction establishes NP-hardness of deciding whether $D_0\le3$ for singleton support, and therefore NP-hardness of computing $D_\epsilon$. I found no substantive gaps, false steps, or necessary expositional repairs.
The two cited results have the required scope:
These match the source arrangements and the eventual simple straight-line arrangement used in the proof. The source representation is also legitimate: the paper discusses combinatorial representations and polynomial-time extraction of the oriented-matroid data from the hardness construction. [Bhangale–Kopparty, Theorem 1.5, representation discussion, and Lemma 2.3](https://arxiv.org/pdf/1503.04486).
The equivalence between stretchability and the prover’s planar realizability condition is justified:
$$ 1+\sum_{k=1}^{n}k = 1+\frac{n(n+1)}2 = N. $$
Choosing adjacent cells across each pseudoline supplies the asserted pair differing in exactly that coordinate. In particular, every coordinate takes both signs.
Assessment: correct; the cited theorem’s hypotheses are satisfied.
The vertex count is correct:
$$
n+2N+1=n^2+2n+3.
$$
The auxiliary heights are pairwise distinct:
The edge rules cover every ordered pair of distinct vertices without conflict. For line-to-line comparisons, the index order is consistent: the prescribed sign from $r_i$ to $r_k$ is $\alpha_{ik}$.
The construction uses only finite combinatorial data. No numerical realization is required as part of the reduction.
Assessment: correct and complete.
Opposite endpoint signs ensure that $q_i$ lies strictly inside the chosen segment and satisfies $f_i(q_i)=0$.
For every $k\ne i$, both endpoint values of $f_k$ have the same strict sign $\alpha_{ki}$. Their convex combination retains that sign, so
$$
\operatorname{sign}(f_k(q_i))=\alpha_{ki}.
$$
Thus every value $f_i(Y_w)$ used in an off-diagonal comparison is nonzero and has the required sign, including comparisons with other line vertices.
The minimum defining $\delta$ ranges over finitely many positive quantities and is therefore positive. Its stated bound gives
$$
\delta\,|h(r_i)-h(w)|<|f_i(Y_w)|.
$$
The expenditure calculation is correct:
$$
p_{r_i}\cdot(x_{r_i}-x_w)
=
f_i(Y_w)+\delta(h(r_i)-h(w)).
$$
The perturbation cannot change the strict sign. All remaining rows use vertical prices, so their expenditure differences equal their distinct height differences. This checks every off-diagonal comparison.
Every preliminary price has positive third coordinate. A single sufficiently large $K$ therefore makes both other coordinates of every transformed price positive.
The matrix $T$ is invertible, and the paired transformation preserves expenditure differences:
$$
(Tp_w)^T T^{-T}(x_w-x_z)
=
p_w^T(x_w-x_z).
$$
A common translation makes every transformed bundle nonnegative without changing any difference. The resulting prices are positive, hence nonnegative and nonzero, as required.
The numerical choices serve only to establish existence; their bit complexity is irrelevant to constructing the output graph.
Assessment: correct; all RP domain restrictions and strict inequalities are verified.
Padding a realization of dimension below three with zero coordinates preserves nonnegative coordinates, nonzero prices, and all strict comparisons.
Since $p_o\ne0$, its zero-expenditure locus $H$ is an affine plane. The prescribed comparisons with each duplicated point pair give opposite strict values of $F_o$, so their segment intersects $H$ strictly between its endpoints.
For every line vertex, the two endpoint values have the same strict prescribed sign. Affinity therefore gives
$$
\operatorname{sign}(F_{r_i}(z_j))=\sigma_i^j.
$$
The adjacent-pair witnesses ensure that each restricted function takes both signs on the selected points of $H$. Hence it is nonconstant. Under affine coordinates on $H$, it has precisely the form required in the definition of planar realizability, with a nonzero linear coefficient.
This argument remains valid even when the original RP realization has dimension below three; it does not assume full-dimensional bundles.
Assessment: correct; there is no missing nondegeneracy assumption.
The sign-vector list has polynomial size. Enumerating cells and propagating their signs through a wiring diagram is a polynomial combinatorial operation.
Comparing all vector pairs costs $O(nN^2)$ coordinate comparisons. Constructing the graph costs $O(m^2)$ comparisons. The stated conservative bit-operation bound is polynomial, and the adjacency matrix has polynomial output size.
The singleton society satisfies all task requirements. With its entire mass concentrated on $G$ and $\epsilon=0$,
$$
D_0=\operatorname{RPDim}(G).
$$
Consequently the proved equivalence gives a polynomial-time many-one reduction to the threshold problem. Computing the quantile and comparing its value with three decides that threshold.
Assessment: the claimed NP-hardness follows. No assumption that the threshold problem belongs to NP is needed or asserted.
The dimension-$m$ construction is valid: every price is nonnegative and nonzero because its diagonal coordinate is one. For distinct vertices, the expenditure difference is exactly one on edges and negative one on nonedges.
Thus every graph is realizable, padding preserves feasibility, and
$$
1\le D_\epsilon\le m.
$$
The case $m=1$ is covered: there are no off-diagonal comparisons, and dimension one suffices.
Threshold feasibility is monotone in dimension. Binary search over the $m$ possible values therefore uses at most $\lceil\log_2m\rceil$ threshold evaluations, each requiring $\tau$ oracle calls.
The arithmetic bounds are consistent with binary rational input:
The stated additional-work bound
$$
O\!\left(\tau m^2+\tau L^2+\tau L\log(m+1)\right)
$$
is consequently valid as an oracle-overhead bound. It is correctly distinguished from the unknown cost of the RP-dimension oracle.
Assessment: correct.
No repair is required. The output resolves the assigned complexity question for the continuous RP model with the specified nonnegative prices and bundles, independently varying realizations, strict off-diagonal comparisons, and adjacency-matrix encoding.
⟨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.