<p>Let <span class="math-container">$P$</span> be a polytope defined by <span class="math-container">$Ax = b, x \geq 0$</span>. </p>

<p><strong>Question:</strong> What is the complexity of computing the total number of faces of <span class="math-container">$P$</span>?</p>

<p>I know counting vertices is <span class="math-container">$\# P$</span>-complete, but this problem is potentially different. Does anyone know if it is has been studied before, and where to find the known results?</p>

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

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

<p>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: <a href="https://mathoverflow.net/questions/342756/polynomial-size-embeddings-of-toric-varieties-from-polytopes">https://mathoverflow.net/questions/342756/polynomial-size-embeddings-of-toric-varieties-from-polytopes</a>, where counting <span class="math-container">$\mathbb{F}_2$</span> points can be done FPT in the treewidth using the results here <a href="https://arxiv.org/pdf/1411.1745.pdf" rel="nofollow noreferrer">https://arxiv.org/pdf/1411.1745.pdf</a> (if I'm interpreting Thm 29 correctly) - provided one could write down equations for the variety and find low dimensional embeddings. </p>

<p>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 <span class="math-container">$F_2$</span> points in a fixed parameter tractable way. It would be interesting, therefore, if this problem was <span class="math-container">$\# P$</span> hard. </p>

CC BY-SA 4.0
2019-10-10T20:33:45.317Z
Just to confirm, you are counting all faces of all dimensions?
Sasho Nikolov
CC BY-SA 4.0
2019-10-10T20:37:46.990Z
@SashoNikolov yes.
Elle Najt
<counting-complexity><polytope>
Is counting the total number of faces of a polytope $\#P$ hard?
Elle Najt
# Is counting the total number of faces of a polytope $\#P$ hard?

(Asked by: username_0 on 2019-10-10)

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.

**Tags:** counting-complexity, polytope

> **Comments:**
> **username_1**: Just to confirm, you are counting all faces of all dimensions?  
> **username_0**: @SashoNikolov yes.  

---

## 0 answers

