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


1 Answer 1


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

  • $\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$
    – Simd
    Sep 11, 2013 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, 2013 at 19:41

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.