NP-hardness conjecture for recognizing f-vectors of fixed-dimensional polytopes

About 5 years old · traced to

Let d≥4d\ge 4 be fixed. An ff-vector is a vector recording the face numbers of a dd-polytope, here written as

f=(1,f0,…,fd−1).f=(1,f_0,\ldots,f_{d-1}).

NP-hardness conjecture. It is NP-hard to decide if a given NN-bit vector f=(1,f0,…,fd−1)f=(1,f_0,\ldots,f_{d-1}) of positive integers is the ff-vector of a dd-polytope.

This conjecture is proposed as an explanation for why the ff-vectors of dd-polytopes are poorly understood when d≥4d\ge 4. Its status is not specified in the source.

References

Primary source

Eran Nevo, “Embedding Divisor and Semi-Prime Testability in f-vectors of polytopes”, arXiv:2109.08220 (2021).

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.