0
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ What is $n$? Dimension? $\endgroup$ – Sasho Nikolov Nov 5 '17 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$ – Joshua Grochow Nov 20 '17 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$ – T.... Nov 20 '17 at 0:43
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Is the natural polytope from cnf convex? $\endgroup$ – T.... Nov 5 '17 at 3:22
  • 2
    $\begingroup$ Yes, it is convex, because it is the intersection of halfspaces. $\endgroup$ – Sasho Nikolov Nov 5 '17 at 3:50

Your Answer

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

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