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

From papers

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

f=(1,f0,,fd1).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,,fd1)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 d4d\ge 4. Its status is not specified in the source.

Progress summary

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

Sources & referencesView supporting material

Primary source

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

Solutions 0

No solutions have been posted yet.