Ist es in NP zu prüfen, ob die konvexe Hülle die Einheitskugel enthält?

Bei einer Menge von Punkten im dimensionalen euklidischen Raum besteht das Problem darin, zu bestimmen, ob die konvexe Hülle die am Ursprung zentrierte Einheitskugel enthält. $n$ $d$

Ist das Problem in NP?

Es ist in Co-NP, da man als Zeuge einen Punkt in der Kugel außerhalb der konvexen Hülle geben und diese Tatsache durch lineare Programmierung überprüfen kann.

Mein Fokus liegt hier nicht auf Computerpräzision in Bezug auf Quadratwurzeln, obwohl dies auch interessant sein kann.

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

cc.complexity-theory cg.comp-geom Oktonoten
quelle

Antworten:

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

Yury
quelle

Dies scheint zu implizieren, dass das Problem sowohl NP-hart als auch im Co-NP ist. Bedeutet dies nicht, dass Co-NP NP enthält, was (gelinde gesagt) ziemlich überraschend erscheint? Oder ist das nicht richtig?

Oktonoten

Das Problem liegt im Co-NP; es ist co-NP vollständig. Es ist NP-schwer, Reduktionen zu kochen.

Yury