NP-hardness conjecture for recognizing f-vectors of fixed-dimensional polytopes
NP-hardness conjecture for recognizing f-vectors of fixed-dimensional polytopes
Let be fixed. An -vector is a vector recording the face numbers of a -polytope, here written as
NP-hardness conjecture. It is NP-hard to decide if a given -bit vector of positive integers is the -vector of a -polytope.
This conjecture is proposed as an explanation for why the -vectors of -polytopes are poorly understood when . 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
Sign in to submit a solution.
No solutions have been posted yet.