Известно, что определение того, является ли данное триангулированное 3-многообразие 3-сферой, входит в NP посредством работы Сола Шлеймера в 2004 году: «Распознавание сфер лежит в NP» arXiv: math / 0407047v1 [math.GT] . Я задаюсь вопросом, было ли это установлено, чтобы быть законченным NP за прошлые пять или шесть лет? Аналогичные задачи, такие как проблема рода 3-многообразных узлов, были показаны NP-полными.
cc.complexity-theory
reference-request
open-problem
topology
Джозеф О'Рурк
источник
источник
Ответы:
Если он NP-полон, то разве вы не доказали бы, что ни один набор (равномерно) вычислимых инвариантов полиномиального времени 3-многообразий не отличает 3-сферы от других 3-многообразий. Я был бы очень удивлен, если бы это было известно.
источник
Просто чтобы добавить к ответу Питера: Хасс, Лагариас и Пиппенгер показали, что проблема узлов в трёх сферах в узлах не существует. Ян Агол доказал, что проблема с узлами в co-NP (но смотрите его комментарии к MathOverflow). По крайней мере, мне кажется, что проблема распознавания трех сфер гораздо больше похожа на неузлобленность, чем на то, чтобы связать род в общем случае трех многообразий. (Потому что это подтверждается наличием положительной эйлеровской характеристической поверхности.)
Таким образом, я хотел бы поспорить, что признание трех сфер также в со-NP. Шаг в этом направлении состоял бы в том, чтобы показать, что распознавание неприводимых тороидальных многообразий происходит в NP непосредственно после Agol. Немного сильнее было бы показать, что распознавание многообразия Хакена лежит в NP. Отделить три сферы от неприводимых неториоидальных многообразий сложнее. Но, возможно, здесь нужно использовать геометрию - если многообразие замкнутое, ориентируемое, неприводимое и атороидальное, то оно имеет одну из восьми геометрий Терстона. Возможно, легко сертифицировать все геометрические, но не гиперболические многообразия, скажем, с помощью почти нормальных расщеплений Хегора. (Хотя границы сложности Хасса, Лагарии и Пиппенгера должны быть как-то заменены.)
источник
Эта статья показывает (хотя я не проверял это), что 3-сфера распознавания * в coNP, предполагая GRH:
(Возможный интерес: в последующей статье arXiv: 1610.04092 [math.GT] это используется для разработки алгоритма, использующего базы Гробнера.)
* Технически заявлено, что распознавание 3-сферы среди 3-сфер с целочисленной гомологией происходит в coNP, предполагая GRH. Я не эксперт в этой области, но мне кажется, что можно вычислить целочисленную гомологию с учетом триангуляции в поли-времени, и если целочисленная гомология не совпадает с гомологией 3-сферы, то это определенно не 3-сфера.
источник