9
$\begingroup$

Let $P$ be a polytope defined by $Ax = b, x \geq 0$.

Question: What is the complexity of computing the total number of faces of $P$?

I know counting vertices is $\# P$-complete, but this problem is potentially different. Does anyone know if it is has been studied before, and where to find the known results?

Motivation: (I think this question is intrinsically interesting, but this "motivation" is just a description of how I came to it.)

As noted here https://math.stackexchange.com/questions/3377451/is-smoothness-required-in-order-for-this-mathbbf-p-point-counting-formula-t , this (appears to be) the number of $\mathbb{F}_2$ points of the corresponding toric variety.

It's plausible to me that this is possible to compute in a fixed parameter tractability kind of way, depending on the description of that toric variety. This hunch is similar to what I was asking about here: https://mathoverflow.net/questions/342756/polynomial-size-embeddings-of-toric-varieties-from-polytopes, where counting $\mathbb{F}_2$ points can be done FPT in the treewidth using the results here https://arxiv.org/pdf/1411.1745.pdf (if I'm interpreting Thm 29 correctly) - provided one could write down equations for the variety and find low dimensional embeddings.

However, it's starting to seem that that approach via finding small embeddings will not be fruitful in general, because there are obstructions to finding polynomial size embeddings. But maybe there are other ways to count the $F_2$ points in a fixed parameter tractable way. It would be interesting, therefore, if this problem was $\# P$ hard.

$\endgroup$
  • $\begingroup$ Just to confirm, you are counting all faces of all dimensions? $\endgroup$ – Sasho Nikolov Oct 10 at 20:33
  • $\begingroup$ @SashoNikolov yes. $\endgroup$ – Lorenzo Najt Oct 10 at 20:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.