Вопросы с тегом «topology»

Топология - исследование объектов, которые можно непрерывно деформировать в другие объекты, не разрывая и не делая дыр в объекте. Это также может означать семейство множеств, обладающих свойством топологического пространства. Свойства - сходимость, связность и непрерывность.

74
Примеры «несвязанной» математики, играющей фундаментальную роль в TCS?

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

61
Применение топологии в информатике

Я хотел бы написать обзор по применению топологии в информатике. Я планирую осветить историю топологических идей в области компьютерных наук, а также выделить несколько текущих событий. Было бы чрезвычайно полезно, если бы кто-то мог дать вклад по любому из вопросов ниже. Существуют ли какие-либо...

28
Ограниченные входные биекции бесконечных последовательностей

Вот загадка, которую мне не удалось решить. Я хотел бы знать, если эта проблема уже известна, или имеет простое решение. Можно определить биекцию используя свойства бикартезианских замкнутых категорий. Андрей Бауэр опубликовал объяснение того, что это значит, в своем блоге как « Конструктивный...

28
Почему «топологическая сортировка» топологическая?

Почему «топологическая сортировка» называется «топологической»? Только потому, что он определяет порядок без изменения каких-либо вершин или ребер - как пончик и кофейная чашка топологически эквивалентны? Почему это не называется "сортировка по зависимости" или что-то еще? Почему "топологический"?...

27
Сложность топологических свойств.

Я ученый, изучающий топологию (разброс топологии точечных множеств, сильно приправленный теорией континуума). Я заинтересовался решением проблем, проверяя описание пространства (с помощью симплексов) для топологических свойств; сохранились до гомеоморфизма. Например, известно, что определение рода...

23
Признание узла как доказательство работы

В настоящее время биткойн имеет систему проверки работоспособности (PoW) с использованием SHA256. Другие хеш-функции используют графы доказательства работы системы, частичное обращение хеш-функций. Можно ли использовать проблему принятия решений в теории узлов, такую ​​как распознавание узлов, и...

22
Статьи о связи между вычислительной сложностью и алгебраической геометрией / топологией?

Мне было интересно, какие бумаги я должен прочитать, чтобы понять этот вопрос Неожиданная связь с другими областями математики, такими как алгебраическая геометрия или высшие когомологии. Возможно, даже область математики еще не разработана. Возможно, кто-то разработает совершенно новое направление...

19
Существует ли геометрическая картина для адиабатических квантовых вычислений?

В адиабатических квантовых вычислениях (AQC) каждый кодирует решение задачи оптимизации в основном состоянии [проблемы] гамильтониана . Чтобы добраться до этого основного состояния, вы начинаете в легко охлаждаемом начальном (основном) состоянии с гамильтонианом и «отжигом» (адиабатически...

18
Топологическое пространство, связанное с SAT: оно компактно?

Проблема удовлетворенности является, конечно, фундаментальной проблемой в теоретической CS. Я играл с одной версией проблемы с бесконечным количеством переменных. \newcommand{\sat}{\mathrm{sat}} \newcommand{\unsat}{\mathrm{unsat}} Базовая настройка. Пусть непустое и, возможно, бесконечное множество...

16
Запрещенные миноры для графов с ограниченным родом

Хорошо известно, что K5K5K_5 и K3,3K3,3K_{3,3} являются запрещенными минорами для плоских графов. Существуют сотни запрещенных миноров для графов, встраиваемых в тор. Количество запрещенных миноров для графов, встраиваемых на поверхность рода g, является экспоненциальной функцией от g . Мой вопрос...

16
В какой степени математика Реалов может быть применена к вычислимым Реалам?

Существует ли общая теорема, которая при надлежащей дезинфекции утверждает, что наиболее известные результаты, касающиеся использования действительных чисел, могут фактически использоваться при рассмотрении только вычислимых вещественных чисел? Или существует правильная характеристика результатов,...

15
Приложения для теории множеств, порядковой теории, бесконечной комбинаторики и общей топологии в информатике?

Я математик, интересующийся теорией множеств, порядковой теорией, бесконечной комбинаторикой и общей топологией. Есть ли приложения для этих предметов в информатике? Я немного посмотрел и нашел много приложений (конечно) для теории конечных графов, конечной топологии, низкоразмерной топологии,...

14
Подходы к GI, вдохновленные проблемой узлов

GI и проблема узлов являются проблемой определения структурной эквивалентности математических объектов. Есть ли какие-либо результаты установления связей между ними? Хорошие связи проблемы узлов со статистической физикой были изучены с помощью полиномов узлов , есть ли похожие результаты для ?G...

13
Является ли проблема 3-сфера распознавания NP-полной?

Известно, что определение того, является ли данное триангулированное 3-многообразие 3-сферой, входит в NP посредством работы Сола Шлеймера в 2004 году: «Распознавание сфер лежит в NP» arXiv: math / 0407047v1 [math.GT] . Я задаюсь вопросом, было ли это установлено, чтобы быть законченным NP за...

10
В какой области теории может использоваться дополнительная структура, присутствующая в метрических пространствах?

Глава Смита в руководстве по логике в области компьютерных наук и другие ссылки описывают, как метрические пространства могут использоваться в качестве областей. Я понимаю, что полные метрические пространства дают уникальные неподвижные точки, но я не понимаю, почему метрические пространства важны....

10
Сложность поиска точки Борсук-Улам

Теорема Борсука-Улама говорит, что для любой непрерывной нечетной функции из n-сферы в евклидово n-пространство существует точка такая, что .х 0 г ( х 0 ) = 0гggИкс0x0x_0г( х0) = 0g(x0)=0g(x_0)=0 Simmons и Su (2002) описывают метод аппроксимации точки с использованием леммы Такера . Однако не ясно,...

9
Какие интересные применения гомотопической алгебры в теоретической информатике?

Я теоретик гомотопии, интересуюсь информатикой. Я хотел бы спросить, каковы некоторые интересные применения гомотопической алгебры (модельные категории, бесконечные категории, симплициальные категории и т. Д.) В теоретической...