¿Está en NP verificar si el casco convexo contiene la bola de la unidad?

Dado un conjunto de puntos en el espacio euclidiano dimensional, el problema es determinar si el casco convexo contiene la bola unitaria centrada en el origen. $n$ $d$

¿Es este problema en NP?

Está en co-NP, ya que uno puede dar un punto en la pelota fuera del casco convexo como testigo y verificar este hecho mediante programación lineal.

Mi enfoque aquí no está en la precisión de la computadora en relación con las raíces cuadradas, aunque esto también puede ser interesante.

(Relacionado con /mathpro/141782/efficiently-determine-if-convex-hull-contains-the-unit-ball .)

cc.complexity-theory cg.comp-geom octonots
fuente

Respuestas:

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

Yury
fuente

Esto parece implicar que el problema es NP-hard y co-NP. ¿No implica esto que co-NP contiene NP que parece bastante sorprendente (por decir lo menos). ¿O eso no está bien?

octonots

El problema está en co-NP; es co-NP completo. Es NP-hard wrt para cocinar reducciones.

Yury