10
$\begingroup$

Given a set of $n$ points in $d$ dimensional Euclidean space, the problem is to determine if the convex hull contains the unit ball centered at the origin.

Is this problem in NP?

It is in co-NP as one can give a point in the ball outside the convex hull as a witness and verify this fact using linear programming.

My focus here is not in computer precision relating to square roots although this may also be interesting.

(Related to https://mathoverflow.net/questions/141782/efficiently-determine-if-convex-hull-contains-the-unit-ball .)

$\endgroup$
7
$\begingroup$

The problem is NP-hard; see my answer at mathoverflow. Thus there is no polynomial-size certificate that the unit ball is contained in the convex hull of given points unless $\text{NP} = \text{co-NP}$ (if $\text{NP} = \text{co-NP}$ then the polynomial hierarchy collapses).

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ This seems to imply the problem is both NP-hard and in co-NP. Doesn't this imply that co-NP contains NP which seems rather surprising (to say the least). Or is that not right? $\endgroup$ – octonots Sep 11 '13 at 19:37
  • 2
    $\begingroup$ The problem is in co-NP; it is co-NP complete. It is NP-hard w.r.t. to Cook reductions. $\endgroup$ – Yury Sep 11 '13 at 19:41

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.