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.

  • 3
    $\begingroup$ What is $n$? Dimension? $\endgroup$ Commented Nov 5, 2017 at 1:39
  • $\begingroup$ 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... $\endgroup$ Commented Nov 20, 2017 at 0:15
  • $\begingroup$ width smallest gap of two linear functionals enclosing the polytope and this is right measure and it influences Lenstra's result as well. $\endgroup$
    – Turbo
    Commented Nov 20, 2017 at 0:43

1 Answer 1


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

  • $\begingroup$ Is the natural polytope from cnf convex? $\endgroup$
    – Turbo
    Commented Nov 5, 2017 at 3:22
  • 2
    $\begingroup$ Yes, it is convex, because it is the intersection of halfspaces. $\endgroup$ Commented Nov 5, 2017 at 3:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.