Простая комплексная задача распознавания

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

Фон

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

Проблема гомеоморфизма

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

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

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

Проблема распознавания

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

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

Проблема с коллектором

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

Ссылки

^ Стиллвелл, Джон (1993), Классическая топология и комбинаторная теория групп , Тексты для аспирантов по математике, том. 72, Спрингер, с. 247, ISBN 9780387979700 .
^ Jump up to: ^а ^б ^с Пунен, Бьорн (25 октября 2014 г.). «Неразрешимые проблемы: сэмплер». arXiv : 1204.0299 [ math.LO ].
^ «А. Марков, «Неразрешимость проблемы гомеоморфии», Докл. АН СССР, 121:2 (1958), 218–220» . www.mathnet.ru . Проверено 27 ноября 2022 г.
^ Матвеев, Сергей (2003), Матвеев, Сергей (ред.), «Алгоритмическое распознавание S3» , Алгоритмическая топология и классификация трехмерных многообразий , Алгоритмы и вычисления в математике, том. 9, Берлин, Гейдельберг: Springer, стр. 193–214, doi : 10.1007/978-3-662-05102-3_5 , ISBN. 978-3-662-05102-3 , получено 27 ноября 2022 г.

[1] Стиллвелл, Джон (1993), Классическая топология и комбинаторная теория групп , Тексты для аспирантов по математике, том. 72, Спрингер, с. 247, ISBN 9780387979700 .

[:0-2] Jump up to: ^а ^б ^с Пунен, Бьорн (25 октября 2014 г.). «Неразрешимые проблемы: сэмплер». arXiv : 1204.0299 [ math.LO ].

[3] «А. Марков, «Неразрешимость проблемы гомеоморфии», Докл. АН СССР, 121:2 (1958), 218–220» . www.mathnet.ru . Проверено 27 ноября 2022 г.

[4] Матвеев, Сергей (2003), Матвеев, Сергей (ред.), «Алгоритмическое распознавание S3» , Алгоритмическая топология и классификация трехмерных многообразий , Алгоритмы и вычисления в математике, том. 9, Берлин, Гейдельберг: Springer, стр. 193–214, doi : 10.1007/978-3-662-05102-3_5 , ISBN. 978-3-662-05102-3 , получено 27 ноября 2022 г.

[1]

[2]

[3]

[4]