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

43
Объяснение теории геометрической сложности в стиле Википедии

Может ли кто-нибудь дать краткое объяснение подхода Малмулей к GCT, понятное неспециалистам? Объяснение, которое подойдет для страницы Википедии по этой теме (которая на данный момент является заглушкой). Мотивация: я «читаю» книгу Скотта Ааронсона «Квантовые вычисления» со времен Демокрита с моим...

38
Программа Малмули GCT

Иногда утверждают, что теория геометрической сложности Кетана Малмулей является единственной правдоподобной программой для решения открытых вопросов теории сложности, таких как вопрос P против NP. Было несколько положительных комментариев от известных теоретиков сложности о программе. По словам...

38
Обязательное условие для изучения GCT

Кажется, что теория геометрической сложности требует больших знаний математики, таких как алгебраическая геометрия, теория представлений. Хотя я учусь на CS и не занимаюсь классами очень абстрактной и чистой математики, мне интересна эта программа. Есть ли список «минимальных знаний» для изучения...

37
Имеет

Насколько я понимаю, программа теории геометрической сложности пытается разделить , доказав, что постоянство комплексной матрицы гораздо сложнее вычислить, чем определитель.VP≠VNPVP≠VNPVP \neq VNP Вопрос, который у меня возник после просмотра документов GCT: будет ли это сразу означать , или это...

31
Насколько сложно использовать подход Mulmuley-Sohoni GCT, чтобы показать * известные * разделения сложности?

В этом гостевом посте Джоша Грохова в блоге о сложности он рассказывает о недавнем семинаре, посвященном GCT, который прошел в Принстоне в июле. Несколько участников утверждали, что мы должны использовать GCT, чтобы атаковать более простые проблемы, чем против N PпP\mathsf{P}Н ПNP\mathsf{NP} ,...

25
Конструктивность в естественном доказательстве и геометрической сложности

Недавно Райан Уилламс доказал, что конструктивность в естественном доказательстве неизбежно приводит к разделению классов сложности: и . N E X PNЕИксп\mathsf{NEXP}Т С0TС0\mathsf{TC}^{0} Конструктивность в естественном доказательстве - это условие, которому удовлетворяют все комбинаторные...

22
Как геометрический подход Малмулей-Сохони к получению нижних оценок позволяет избежать естественных доказательств (в смысле Разборова-Рудича)?

Точная формулировка названия принадлежит Ананду Кулькарни (который предложил создать этот сайт). Этот вопрос был задан в качестве примера вопроса, но мне безумно любопытно. Я очень мало знаю об алгебраической геометрии, и на самом деле у меня есть только беглое понимание студентами препятствий,...

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

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

17
Состояние нижних границ контуров для контуров глубины, ограниченных полилогом

Сложность схемы с ограниченной глубиной является одной из основных областей исследования в теории сложности схемы. Эта тема имеет происхождение в результатах типа «функция четности не в » и « функция mod не вычисляется », где - класс языков, разрешимых по неоднородности, постоянной глубине,...

9
Нормирующая лемма Нётера для конечных полей

Мой вопрос о теоремах 4.1 и 4.2 в "Теории геометрической сложности V" . Первая теорема утверждает, что существует алгоритм EXPSPACE для построения hsop дляΔ[det,m]Δ[det,m]\Delta[\text{det},m] (см. определения в документе) на CC\mathbb{C} (фактически на произвольном алгебраически замкнутом поле...