NP-hardness of maximal angle computation for the nonnegative orthant

Let QRnQ\subseteq\mathbb R^n be a polyhedral cone, and let MA(P,Q){\rm MA}(P,Q) denote the problem of computing the maximal angle between cones PP and QQ. Orthant-restriction conjecture. Computing the maximal angle between R+n\mathbb R^n_+ and a polyhedral cone QRnQ\subseteq\mathbb R^n is NP-hard, that is, solving MA(R+n,Q){\rm MA}(\mathbb R^n_+,Q) is NP-hard. The preceding result establishes NP-hardness when the first cone is generated by a subset of the canonical basis; the conjecture asks whether NP-hardness persists when the first cone is the full nonnegative orthant.

Sources & referencesView supporting material

Primary source

Giovanni Barbarino, Nicolas Gillis and David Sossa, “Computing cone-constrained singular values of matrices”, arXiv:2504.04069 (2026).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.