# Is it in NP to check if the convex hull contains the unit ball?

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.

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

• 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? – octonots Sep 11 '13 at 19:37
• The problem is in co-NP; it is co-NP complete. It is NP-hard w.r.t. to Cook reductions. – Yury Sep 11 '13 at 19:41