1
$\begingroup$

Volume computation is $\#P$ hard.

Take the $[0,1]^n$ polytope.

Slice it by an half space inequality with $poly(n)$ bit rational coefficients into two unequal halves.

Volume of bigger section is $\frac12+\epsilon$ where $\epsilon\in(0,\frac12)$ holds.

  1. Is there an efficient polynomial time deterministic algorithm to find $\frac pq$ where each integer $p$ and $q$ are of $poly(n)$ bits so that we can achieve $|\frac pq-\epsilon|<\frac1{poly(n)}$?

  2. Related Diophantine problem is if each integer $p$ and $q$ are of $poly(n)$ bits then what is the smallest $$|\frac pq-\epsilon|$$ we can achieve regardless of being bound in polynomial time when the half space inequality has $poly(n)$ bit rational coefficients?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

This seems to be quasi-done in.

Marichal, Jean-Luc; Mossinghoff, Michael J., Slices, slabs, and sections of the unit hypercube, Online J. Anal. Comb. 3, Article 1, 11 p. (2008). ZBL1189.52011.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Seems like closed formula exists however good enough for polynomial time? $\endgroup$
    – Turbo
    Commented Jul 19, 2019 at 0:03
  • $\begingroup$ @Turbo Looks like it to me - some of products. $\endgroup$
    – Igor Rivin
    Commented Jul 19, 2019 at 0:29
  • $\begingroup$ Which products are in polynomial time? $\endgroup$
    – Turbo
    Commented Jul 19, 2019 at 0:32
  • 1
    $\begingroup$ Isn't the relevant formula (3)? It's not clear to me why the sum can be computed in polynomial time, although maybe I am missing a trick. $\endgroup$
    – Sasho Nikolov
    Commented Jul 19, 2019 at 0:58

You must log in to answer this question.