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.
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.