<p>The problem is NP-hard; see my answer at <a href="https://mathoverflow.net/questions/141782/efficiently-determine-if-convex-hull-contains-the-unit-ball">mathoverflow</a>. 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).</p>

CC BY-SA 3.0
2013-09-11T19:37:44.157Z
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?
Simd
CC BY-SA 3.0
2013-09-11T19:41:58.417Z
The problem is in co-NP; it is co-NP complete. It is NP-hard w.r.t. to Cook reductions.
Yury
CC BY-SA 3.0
2013-09-11T19:26:04.173Z
2013-09-11T19:26:04.173Z
2017-04-13T12:57:54.777Z
Yury
<p>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. </p>

<blockquote>
  <p>Is this problem in NP?</p>
</blockquote>

<p>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.  </p>

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

<p>(Related to <a href="https://mathoverflow.net/questions/141782/efficiently-determine-if-convex-hull-contains-the-unit-ball">https://mathoverflow.net/questions/141782/efficiently-determine-if-convex-hull-contains-the-unit-ball</a> .)</p>

<cc.complexity-theory><cg.comp-geom>
Is it in NP to check if the convex hull contains the unit ball?
Simd
# Is it in NP to check if the convex hull contains the unit ball?

(Asked by: username_0 on 2013-09-11)

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

**Tags:** cc.complexity-theory, cg.comp-geom


---

## 1 answers

### Answer by username_1 on 2013-09-11. Score: 7 | Accepted answer

The problem is NP-hard; see my answer at [mathoverflow](https://mathoverflow.net/questions/141782/efficiently-determine-if-convex-hull-contains-the-unit-ball). 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).

> **Comments:**
> **username_0**: 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?  
> **username_1**: The problem is in co-NP; it is co-NP complete. It is NP-hard w.r.t. to Cook reductions.  

---

