Это в NP, чтобы проверить, содержит ли выпуклый корпус единичный шар?

Для заданного набора из точек в мерном евклидовом пространстве задача состоит в том, чтобы определить, содержит ли выпуклая оболочка единичный шарик с центром в начале координат. $n$ $d$

Эта проблема в NP?

Это в co-NP, поскольку можно указать точку в шаре вне выпуклой оболочки в качестве свидетеля и проверить этот факт с помощью линейного программирования.

Мой фокус здесь не на компьютерной точности, связанной с квадратными корнями, хотя это также может быть интересно.

(Относится к /mathpro/141782/efficiently-determine-if-convex-hull-contains-the-unit-ball .)

cc.complexity-theory cg.comp-geom octonots
источник

Ответы:

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

Юрий
источник

Это, кажется, подразумевает, что проблема как в NP-hard, так и в co-NP. Разве это не означает, что в совместном NP есть NP, что кажется довольно удивительным (если не сказать больше). Или это не правильно?

октоноты

Проблема в со-НП; это со-НП завершено. NP-сложнее, чем готовить сокращения.

Юрий