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

22

Мне было интересно, какие бумаги я должен прочитать, чтобы понять этот вопрос

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

Еще одна формулировка вопроса: «Какие статьи мне следует прочитать, чтобы создать связь между вычислительной сложностью и алгебраической геометрией / топологией?»

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

cc.complexity-theory reference-request gct algebraic-topology Джошуа Герман
источник
1
Могу ли я предложить изменить название? Что-то вроде «Документы о связи между вычислительной сложностью и алгебраической геометрией / топологией».
Каве
Не могли бы вы немного уточнить свой вопрос? Я думаю, что все пропустят что-то из этой строки, если эта строка верна, поскольку он говорит о «неизвестных». Я думаю, что ответ профессора Суреша ниже на нижних границах является хорошей ссылкой.
против
2
Вы также можете посмотреть на этот вопрос: cstheory.stackexchange.com/questions/2898/…
Мартин Шварц,
1
Я также нашел эту статью cs.brown.edu/~mph/HerlihyS99/p858-herlihy.pdf
Джошуа Герман

Ответы:

10
против
источник
Это явный пример этальных когомологий? math.mcgill.ca/goren/SeminarOnCohomology/etale2.pdf
Джошуа Герман
Пожалуйста, обратитесь сюда. www-math.mit.edu/~kedlaya/18.787/intro.pdf
против
1
Работа Судана и Гурусвами в основном посвящена декодированию списков (что, в общем, касается и кодов AG) - тема, которая поднималась в конце 90-х годов и активно развивалась в 2000-х годах. Метод алгебраической геометрии появился в 80-х годах в работах Гоппы и был разработан Цфасманом, Владуцем и многими другими в 90-х годах. Лично я бы предложил работу: Хохольдт, Ван Линт, Пелликаан, Алгебраические геометрические коды, 1998.
Артем Пеленицын
1
Что касается вычислительной AG, я бы предложил книги Кокса-Литтла-О'Ши и Шенка, но эта тема немного не имеет отношения к «связи между вычислительной сложностью и алгебраической геометрией», запрошенной Джошуа.
Артем Пеленицын
4

На слайде 26 Мартин Эскардо предлагает алгоритм, который может дать вам то, что вы ищете:

  1. Иди в библиотеку.
  2. Выберите книгу по топологии.
  3. Выберите теорему.
  4. Применить словарь.
  5. Получить теорему в вычислениях.

http://www.cs.bham.ac.uk/~mhe/.talks/popl2012/escardo-popl2012.pdf

Смотрите также эту статью

NietzscheanAI
источник
2
Словарь представляет собой соответствие между терминами в топологии (например, открытый набор) и вычислимостью (например, полуразрешимый набор).
Митч
может быть, это должен быть принятый ответ
Никос М.
@NikosM. Я бы разорвался с первым ответом, и этот, и принятый ответ был принят некоторое время, так что я бы не стал его менять. Если бы был объединенный ответ со всем, может быть, но тогда этот вопрос, вероятно, стал бы вики сообщества.
Джошуа Герман
@JoshuaHerman, конечно, я понимаю, хотя сам иногда менял принятый ответ, когда мои знания обновлялись, и появлялся другой ответ, более подходящий к вопросу. В любом случае, по этой теме вы обнаружите, что существует много других аналогий с другими областями математики (например, не только между топологией и сложностью). Например, область, которая имеет этот потенциал (и была вдохновлена ​​топологией). такое теория категорий
Никос М.
3

Здесь приведены некоторые недавние ссылки из алгебраической топологии и теории жесткости UGC - теории Морса , а также другие ссылки на гипотезу об уникальных играх и вычислительную топологию . Последнее касается покрытия пространств графов и «подъема» графов и может указывать на более глубокую связь между топологией и гипотезой об уникальных играх.

user3483902
источник