Симплициальная комплексная задача распознавания

Проблема распознавания симплициального комплекса — это вычислительная проблема в алгебраической топологии . Для заданного симплициального комплекса проблема состоит в том, чтобы решить, гомеоморфен ли он другому фиксированному симплициальному комплексу. Проблема неразрешима для комплексов размерности 5 или более. ^{[1] [2] : 9–11}

Абстрактный симплициальный комплекс (ASC) — это семейство множеств, замкнутое относительно взятия подмножеств (подмножество множества в семействе также является множеством в семействе). Каждый абстрактный симплициальный комплекс имеет уникальную геометрическую реализацию в евклидовом пространстве как геометрический симплициальный комплекс (GSC), где каждое множество с k элементами в ASC отображается в ( k -1)-мерный симплекс в GSC. Таким образом, ASC обеспечивает конечное представление геометрического объекта. Учитывая ASC, можно задать несколько вопросов относительно топологии GSC, который он представляет.

Задача гомеоморфизма заключается в следующем: для двух конечных симплициальных комплексов, представляющих гладкие многообразия , решить, являются ли они гомеоморфными .

• Если размерность комплексов не превышает 3, то задача разрешима. Это следует из доказательства гипотезы геометризации .
• Для любого d ≥ 4 проблема гомеоморфизма для d -мерных симплициальных комплексов неразрешима. ^[3]

То же самое верно, если заменить «гомеоморфный» на « кусочно-линейный гомеоморфный ».

Проблема распознавания является подзадачей проблемы гомеоморфизма, в которой один симплициальный комплекс задан как фиксированный параметр. Если в качестве входных данных задан другой симплициальный комплекс, задача состоит в том, чтобы решить, гомеоморфен ли он заданному фиксированному комплексу.

• Проблема распознавания разрешима для 3-мерной сферы . ^[4] То есть, существует алгоритм, который может решить, гомеоморфен ли любой заданный симплициальный комплекс границе 4-мерного шара.${\displaystyle S^{3}}$
• Проблема распознавания неразрешима для d-мерной сферы при любом d ≥ 5. Доказательство проводится сведением к проблеме слов для групп . Из этого можно доказать, что проблема распознавания неразрешима для любого фиксированного компактного d -мерного многообразия с d ≥ 5.${\displaystyle S^{d}}$
• По состоянию на 2014 год остается открытым вопрос о том, разрешима ли проблема распознавания для 4-мерной сферы . ^{[2] : 11}${\displaystyle S^{4}}$

Проблема многообразия : задан конечный симплициальный комплекс, гомеоморфен ли он многообразию ? Проблема неразрешима; доказательство — сведение к проблеме слов для групп . ^{[2] : 11}