Est-ce en NP pour vérifier si la coque convexe contient la boule unitaire?

Étant donné un ensemble de points dans l' espace euclidien de dimension , le problème est de déterminer si la coque convexe contient la boule unitaire centrée à l'origine. $n$ $d$

Ce problème est-il dans NP?

Il est en co-NP car on peut donner un point dans la balle en dehors de la coque convexe comme témoin et vérifier ce fait en utilisant une programmation linéaire.

Je ne m'intéresse pas ici à la précision informatique relative aux racines carrées, bien que cela puisse également être intéressant.

(Lié à /mathpro/141782/efficiently-determine-if-convex-hull-contains-the-unit-ball .)

cc.complexity-theory cg.comp-geom octonots
la source

Réponses:

$\text{NP} = \text{co-NP}$ $\text{NP} = \text{co-NP}$

Yury
la source

Cela semble impliquer que le problème est à la fois NP-dur et co-NP. Cela ne signifie-t-il pas que le co-NP contient du NP, ce qui semble assez surprenant (c'est le moins qu'on puisse dire). Ou n'est-ce pas vrai?

octonots

Le problème est en co-NP; il est co-NP complet. Il est NP-dur d'écrire des réductions sur Cook.

Yury