The BoxContZonotope NP-hardness conjecture

About 10 years old · traced to

Let a1,…,am∈Qna_1,\ldots,a_m\in\mathbb{Q}^n and let ν∈[0,∞)∩Q\nu\in[0,\infty)\cap\mathbb{Q}. BoxContZonotope conjecture. Deciding whether there exists a rectangular box BB such that

∑j=1m[−aj,aj]⊂B,vol⁡n(B)≤ν\sum_{j=1}^m[-a_j,a_j]\subset B,\qquad \operatorname{vol}_n(B)\leq\nu

is NP\mathbb{NP}-hard. The problem is introduced as a further source of computational intractability in determining Λ(P)\Lambda(P), beyond volume computation alone; no proof or resolution is supplied.

References

Primary source

Stefano Campi, Peter Gritzmann and Paolo Gronchi, “On the reverse Loomis-Whitney inequality”, arXiv:1607.07891 (2017).

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.