Czy w NP należy sprawdzić, czy wypukły kadłub zawiera kulę jednostkową?

Biorąc pod uwagę zbiór punktów w wymiarowej przestrzeni euklidesowej, problemem jest ustalenie, czy wypukłe kadłuba zawiera piłka jednostki skupione na pochodzenie. $n$ $d$

Czy to problem w NP?

Jest w ko-NP, ponieważ można dać punkt w kuli poza wypukłym kadłubem jako świadek i zweryfikować ten fakt za pomocą programowania liniowego.

Nie skupiam się tutaj na precyzji komputerowej związanej z pierwiastkami kwadratowymi, chociaż może to być również interesujące.

(Powiązane z /mathpro/141782/fficiently-determine-if-convex-hull-contains-the-unit-ball .)

cc.complexity-theory cg.comp-geom

— oktonoty
źródło

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

— Yury
źródło

Wydaje się to sugerować, że problem jest trudny zarówno dla NP, jak i dla NP. Czy to nie oznacza, że ko-NP zawiera NP, co wydaje się dość zaskakujące (co najmniej). Czy to nie w porządku?

— octonots

Problem tkwi w ko-NP; jest co-NP kompletny. To jest NP-trudne wrt do redukcji Cooka.

— Yury