Геометрическая теория сложности

Геометрическая теория сложности (GCT) — это исследовательская программа в области теории сложности вычислений, предложенная Кетаном Малмули и Милиндом Сохони. Цель программы — ответить на самую известную открытую проблему в информатике — P = NP — показав, что класс сложности P не равен классу сложности NP .

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

Некоторые считают, что этот подход является единственной жизнеспособной действующей в настоящее время программой по отделению P от NP . Однако Кетан Малмули считает, что программа, если она жизнеспособна, вероятно, займет около 100 лет, прежде чем она сможет решить проблему P и NP . ^[1]

Программу реализуют несколько исследователей в области математики и теоретической информатики. Частично причина интереса к программе заключается в существовании аргументов в пользу того, что программа позволяет избежать известных препятствий, таких как релятивизация и естественные доказательства для доказательства общих нижних оценок. ^[2]

Ссылки

^ Фортнау, Лэнс (2009), «Состояние проблемы P и NP», Communications of the ACM , 52 (9): 78–86, CiteSeerX 10.1.1.156.767 , doi : 10.1145/1562164.1562186 , S2CID 5969255 .
^ Малмули, Кетан Д. (1 апреля 2011 г.). «О P против NP и теории геометрической сложности: Шри Рамакришне посвящается» . Журнал АКМ . 58 (2): 5. дои : 10.1145/1944345.1944346 . ISSN 0004-5411 . S2CID 7703175 .

Дальнейшее чтение

К.Д. Малмули и М. Сохони. Геометрическая теория сложности I: подход к P и NP и связанным с этим проблемам. СИАМ Дж. Компьютер. 31(2), 496–526, 2001.

К.Д. Малмули и М. Сохони. Геометрическая теория сложности II: к явным препятствиям для вложений многообразий классов. SIAM J. Comput., 38(3), 1175–1206, 2008.

К.Д. Малмули, Х. Нараянан и М. Сохони. Геометрическая теория сложности III: о решении ненулевого коэффициента Литтлвуда-Ричардсона. Дж. Алгебраическая комбинация. 36 (2012), вып. 1, 103–110.

К.Д. Малмули. Геометрическая теория сложности V: эффективные алгоритмы нётеровской нормализации. Дж. Амер. Математика. Соц. 30 (2017), вып. 1, 225–309. arXiv:1209.5993 [cs.CC]

К.Д. Малмули. Теория геометрической сложности VI: переворот через позитивность. Технический отчет, факультет компьютерных наук Чикагского университета, январь 2011 г.

Внешние ссылки

Страница GCT, Чикагский университет
Описание на веб-странице Института Саймонса
Вопросы GCT по теории cs
в стиле Википедии Объяснение геометрической теории сложности Джошуа Грочоу
Каковы текущие достижения геометрической теории сложности?
https://mathoverflow.net/questions/243011/why-should-algebraic-geometers-and-representation-theorists-care-about-geometric/

[1] Фортнау, Лэнс (2009), «Состояние проблемы P и NP», Communications of the ACM , 52 (9): 78–86, CiteSeerX 10.1.1.156.767 , doi : 10.1145/1562164.1562186 , S2CID 5969255 .

[2] Малмули, Кетан Д. (1 апреля 2011 г.). «О P против NP и теории геометрической сложности: Шри Рамакришне посвящается» . Журнал АКМ . 58 (2): 5. дои : 10.1145/1944345.1944346 . ISSN 0004-5411 . S2CID 7703175 .

[1]

[2]