В этом гостевом посте Джоша Грохова в блоге о сложности он рассказывает о недавнем семинаре, посвященном GCT, который прошел в Принстоне в июле. Несколько участников утверждали, что мы должны использовать GCT, чтобы атаковать более простые проблемы, чем против N P , чтобы построить интуицию и посмотреть, есть ли у метода потенциал.
Вопрос, который меня беспокоил:
Можно ли использовать GCT, чтобы показать известные разделения, такие как или L ≠ P S P A C E ?
Делает что-то вроде
- Даже не имеет смысла в контексте GCT, или
- Совершенно тривиально и неинтересно в рамках GCT, или
- Привести к предположениям так же сложно, как против N P ?
cc.complexity-theory
gct
Мугизи Рвебангира
источник
источник
Ответы:
Краткий ответ: вероятно, нет (1), определенно нет (2) и, возможно, (3).
Это то, о чем я думал сейчас время от времени. Во-первых, в некотором смысле GCT действительно нацелен на то, чтобы дать более низкие оценки вычислительным функциям, а не решению проблем. Но ваш вопрос имеет смысл для версий функциональных классов , P , P S P A C E и E X PL P PSPACE EXP .
Во-вторых, на самом деле доказываем булевы версии - те, которые мы знаем и любим, какFP≠FEXP - вероятно, невероятно сложно в подходе GCT, поскольку это потребовало бы использования теории модульных представлений (теории представлений поверх конечных поля), что не очень хорошо понято в любом контексте.
Но разумная цель может заключаться в использовании GCT , чтобы доказать алгебраический аналог .FP≠FEXP
Чтобы перейти к вашему вопросу: я считаю, что эти вопросы могут быть сформулированы в контексте GCT, хотя не сразу понятно, как. Более или менее вам нужна функция, которая является полной для класса и характеризуется его симметриями; дополнительный бонус, если теорию представления, связанную с функцией, легко понять, но это последнее обычно довольно сложно.
Даже когда вопросы сформулированы в контексте GCT, я понятия не имею , как трудно будет использовать GCT , чтобы доказать (алгебраические аналоги) и т.д. представительские теоретико-домыслы , которые будут возникать в этих контекстах скорее всего, будет иметь вкус, очень похожий на те, что возникают в P против N PFP≠FEXP P NP или постоянный против определителя. Можно надеяться, что классические доказательства этих результатов разделения могут дать некоторое представление о том, как найти теоретико-представительные «препятствия», необходимые для доказательства GCT. Однако доказательства упомянутых вами утверждений - это все теоремы иерархии, основанные на диагонализации, и я не вижу, как диагонализация действительно даст вам глубокое понимание теории представлений, связанной с функцией, которая является полной для (алгебраического аналога) , скажем. С другой стороны, я еще не видел, как сформулировать F E X P в контексте GCT, поэтому пока рано говорить.FEXP FEXP
источник
Есть новая статья об arXiv от Джошуа Грохова , которая показывает, как поместить несколько известных методов нижней границы в структуру GCT, и кажется, что она несколько отвечает на ваш вопрос.
(В основном это просто комментарий, но никто не заметит комментарий, поэтому я публикую его как ответ.)
источник