Given convex polytope $\mathcal P\subseteq\Bbb R^n$ with $\mathcal P_\Bbb Z\leq2^n$ integer points and given locations of $O(\log \mathcal P_\Bbb Z)$ integer points in some positions can we obtain $\mathcal P_\Bbb Z$ in $O(n^c)$ time at a $c>0$?

Does the location of revealed points affect the complexity?


Intuitively, specifying a small number of integer points in a small region of some polytope has almost no connection with the rest of the polytope, so the answer should be negative. To give a concrete example, let $P$ be an $n$-element poset and $\mathcal{O}(P)$ its order polytope (see http://math.mit.edu/~rstan/pubs/pubfiles/66.pdf). If you are given the facets of $\mathcal{O}(P)$ then computing the number of integer points is equivalent to computing the number $j(P)$ of order ideals of $P$ (which is at most $2^n$), and is known to be $\#P$-complete. Suppose $P$ is the disjoint union of an $n/2$-element antichain (say) and an $n/2$-element poset $Q$. Then we know the $(n/2)!$ order ideals of the antichain, which is far more than $\log_2 j(P)\leq n$. Moreover, $j(Q)=(n/2)!j(Q)$, and computing $j(Q)$ is $\#P$-complete. I doubt whether specifying any $n$ (or some much larger number) of order ideals of $P$ will be of much help in counting the total number of them.

  • $\begingroup$ I think (without reading your paper and delving deep) your answer with 'small region' could be taken as qualifying for 'some specially chosen unfavorable points'. How about a set of points chosen with uniform measure or existence of special set of points? $\endgroup$ – Brout Nov 26 '17 at 22:35
  • $\begingroup$ I will have to read your paper to understand the definitions. Thank you for the post. $\endgroup$ – Brout Nov 26 '17 at 22:36
  • $\begingroup$ My intuition is that 'if there are special positions of the polytope in $\Bbb R^n$ that can let it have more points than other positions then there should be special points in the polytope which can give information on whether the polytope is in an abundant position or not and that information might be amplifiable to help count efficiently'. $\endgroup$ – Brout Nov 26 '17 at 22:56

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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