<p>Let's just take the reduction from SAT to IP and see if it works. For a 3-CNF $\phi$, define a polytope $P$ which contains all $x \in \mathbb{R}^n$ satisfying the constraints</p>

<ol>
<li>$0\le x_i \le 1$ for all $i$,</li>
<li>clause constraints for any clause $C$ of $\phi$: for example if $C = x_i \vee \bar{x}_j \vee x_k$ put the constraint $x_i + 1-x_j + x_k \ge 1$. (I trust you can figure out the general rule.)</li>
</ol>

<p>Clearly $P$ has an integer point if and only if $\phi$ is satisfiable. Also the number of integer points in $P$ equals the number of solutions of $\phi$. So as long as the ratio between the diameter and the width of $P$ is polynomial, this answers both your questions.</p>

<p>Let us then compute its diameter and width. $P \subseteq [0,1]^n$, so the diameter of $P$ is at most $\sqrt{n}$. By width, I am assuming you mean the standard</p>

<p>$$
\min_{\theta: \|\theta\|_2 = 1} \max_{x, y \in P} \langle \theta, x-y\rangle,
$$</p>

<p>i.e. the smallest distance between two parallel hyperplanes that sandwich $P$. Notice that any $x$ which satisfies $\frac13 \le x_i \le \frac23$  for all $i$ is in $P$. So, for a $\theta$, pick $x_i$ to be $\frac23$ if $\theta_i &gt; 0$ and $\frac13$ otherwise, and pick $y_i$ to be $\frac13$ if $\theta_i &gt; 0$ and $\frac23$ otherwise. Then:</p>

<p>$$
\langle \theta, x - y \rangle = \sum_{i = 1}^n \frac{|\theta_i|}{3} = \frac13 \|\theta\|_1 \ge \frac13 \|\theta\|_2.
$$</p>

<p>So the width is at least $\frac13$. </p>

CC BY-SA 3.0
2017-11-05T03:22:03.673Z
Is the natural polytope from cnf convex?
Turbo
CC BY-SA 3.0
2017-11-05T03:50:31.087Z
Yes, it is convex, because it is the intersection of halfspaces.
Sasho Nikolov
CC BY-SA 3.0
2017-11-05T02:13:15.920Z
2017-11-05T02:13:15.920Z
Sasho Nikolov
<p>Given a convex polytope let the width of the polytope be $d$ and the farthest euclidean distance between any points in the polytope be $e$.</p>

<p>Denote $\mathcal P(a,c)$ to be the set of convex polytopes in $\Bbb R^n$ presented by $O(n^a)$ linear inequalities with $e/d=O(n^c)$. </p>

<ol>
<li><p>Is it $\#P$ complete to find number of integer points in such polytopes?</p></li>
<li><p>Is it $NP$ complete to decide existence of integer points in such polytopes?</p></li>
</ol>

<p>I am essentially asking if the polytope is reasonably round what is the difficulty of counting and decision problems. Here for quantifying roundedness I use width and max distance (but may be some other quantification which I do not know may be appropriate).</p>

<p>I think some strange partition of 0/1 cube with convex faces might suffice for 1.</p>

CC BY-SA 3.0
2017-11-05T01:39:30.000Z
What is $n$? Dimension?
Sasho Nikolov
CC BY-SA 3.0
2017-11-20T00:15:04.410Z
Also, what is width? I would've thought it was defined as the maximum distance between any two points in the polytope, but apparently it means something different...
Joshua Grochow
CC BY-SA 3.0
2017-11-20T00:43:44.170Z
width smallest gap of two linear functionals enclosing the polytope and this is right measure and it influences Lenstra's result as well.
Turbo
CC BY-SA 4.0
2024-11-23T11:05:24.190Z
This question is similar to: [The number of integral points in a polytope](https://cstheory.stackexchange.com/questions/22280/the-number-of-integral-points-in-a-polytope). If you believe it’s different, please [edit] the question, make it clear how it’s different and/or how the answers on that question are not helpful for your problem.
138 Aspen
<counting-complexity><big-picture><np-complete><polytope><integer-lattice>
On polytope lattice points
Turbo
# On polytope lattice points

(Asked by: username_0 on 2017-11-05)

Given a convex polytope let the width of the polytope be $d$ and the farthest euclidean distance between any points in the polytope be $e$.

Denote $\mathcal P(a,c)$ to be the set of convex polytopes in $\Bbb R^n$ presented by $O(n^a)$ linear inequalities with $e/d=O(n^c)$.

1. Is it $\#P$ complete to find number of integer points in such polytopes?
2. Is it $NP$ complete to decide existence of integer points in such polytopes?

I am essentially asking if the polytope is reasonably round what is the difficulty of counting and decision problems. Here for quantifying roundedness I use width and max distance (but may be some other quantification which I do not know may be appropriate).

I think some strange partition of 0/1 cube with convex faces might suffice for 1.

**Tags:** counting-complexity, big-picture, np-complete, polytope, integer-lattice

> **Comments:**
> **username_1**: What is $n$? Dimension?  
> **username_2**: Also, what is width? I would've thought it was defined as the maximum distance between any two points in the polytope, but apparently it means something different...  
> **username_0**: width smallest gap of two linear functionals enclosing the polytope and this is right measure and it influences Lenstra's result as well.  
> **username_3**: This question is similar to: [The number of integral points in a polytope](https://cstheory.stackexchange.com/questions/22280/the-number-of-integral-points-in-a-polytope). If you believe it’s different, please [edit] the question, make it clear how it’s different and/or how the answers on that question are not helpful for your problem.  

---

## 1 answers

### Answer by username_1 on 2017-11-05. Score: 2 | Accepted answer

Let's just take the reduction from SAT to IP and see if it works. For a 3-CNF $\phi$, define a polytope $P$ which contains all $x \in \mathbb{R}^n$ satisfying the constraints

1. $0\le x\_i \le 1$ for all $i$,
2. clause constraints for any clause $C$ of $\phi$: for example if $C = x\_i \vee \bar{x}\_j \vee x\_k$ put the constraint $x\_i + 1-x\_j + x\_k \ge 1$. (I trust you can figure out the general rule.)

Clearly $P$ has an integer point if and only if $\phi$ is satisfiable. Also the number of integer points in $P$ equals the number of solutions of $\phi$. So as long as the ratio between the diameter and the width of $P$ is polynomial, this answers both your questions.

Let us then compute its diameter and width. $P \subseteq [0,1]^n$, so the diameter of $P$ is at most $\sqrt{n}$. By width, I am assuming you mean the standard

$$
\min\_{\theta: \|\theta\|\_2 = 1} \max\_{x, y \in P} \langle \theta, x-y\rangle,
$$

i.e. the smallest distance between two parallel hyperplanes that sandwich $P$. Notice that any $x$ which satisfies $\frac13 \le x\_i \le \frac23$ for all $i$ is in $P$. So, for a $\theta$, pick $x\_i$ to be $\frac23$ if $\theta\_i > 0$ and $\frac13$ otherwise, and pick $y\_i$ to be $\frac13$ if $\theta\_i > 0$ and $\frac23$ otherwise. Then:

$$
\langle \theta, x - y \rangle = \sum\_{i = 1}^n \frac{|\theta\_i|}{3} = \frac13 \|\theta\|\_1 \ge \frac13 \|\theta\|\_2.
$$

So the width is at least $\frac13$.

> **Comments:**
> **username_0**: Is the natural polytope from cnf convex?  
> **username_1**: Yes, it is convex, because it is the intersection of halfspaces.  

---

