Está em NP verificar se o casco convexo contém a bola unitária?

Dado um conjunto de pontos em espaço Euclideano tridimensional, o problema é determinar se o casco convexo contém a bola unidade centrado na origem. $n$ $d$

Esse problema está no NP?

É em co-NP, como se pode dar um ponto na bola fora do casco convexo como testemunha e verificar esse fato usando programação linear.

Meu foco aqui não está na precisão do computador relacionada às raízes quadradas, embora isso também possa ser interessante.

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

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

Respostas:

O problema é NP-difícil; veja minha resposta em mathoverflow . Portanto, não há certificado de tamanho polinomial de que a bola unitária esteja contida no casco convexo de determinados pontos, a menos que (se a hierarquia polinomial entra em colapso). $\text{NP} = \text{co-NP}$ $\text{NP} = \text{co-NP}$

Yury
fonte

Isso parece implicar que o problema é difícil de NP e co-NP. Isso não implica que o co-NP contenha NP, o que parece bastante surpreendente (para dizer o mínimo). Ou isso não está certo?

Octonots # 11/13

O problema está no co-NP; é co-NP completo. É NP-hard wrt para reduções de Cook.

Yury