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

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

Вопрос, который меня беспокоил:

Можно ли использовать GCT, чтобы показать известные разделения, такие как или L ≠ P S P A C E ?$\mathsf{P} \neq \mathsf{EXP}$$\mathsf{L} \neq \mathsf{PSPACE}$

Делает что-то вроде $\mathsf{L} \neq \mathsf{PSPACE}$

1. Даже не имеет смысла в контексте GCT, или
2. Совершенно тривиально и неинтересно в рамках GCT, или
3. Привести к предположениям так же сложно, как против N P ?$\mathsf{P}$$\mathsf{NP}$

Краткий ответ: вероятно, нет (1), определенно нет (2) и, возможно, (3).

Это то, о чем я думал сейчас время от времени. Во-первых, в некотором смысле GCT действительно нацелен на то, чтобы дать более низкие оценки вычислительным функциям, а не решению проблем. Но ваш вопрос имеет смысл для версий функциональных классов , P , P S P A C E и E X $L$$P$$PSPACE$$EXP$ .

Во-вторых, на самом деле доказываем булевы версии - те, которые мы знаем и любим, как $FP \neq FEXP$ - вероятно, невероятно сложно в подходе GCT, поскольку это потребовало бы использования теории модульных представлений (теории представлений поверх конечных поля), что не очень хорошо понято в любом контексте.

Но разумная цель может заключаться в использовании GCT , чтобы доказать алгебраический аналог .$FP \neq FEXP$

Чтобы перейти к вашему вопросу: я считаю, что эти вопросы могут быть сформулированы в контексте GCT, хотя не сразу понятно, как. Более или менее вам нужна функция, которая является полной для класса и характеризуется его симметриями; дополнительный бонус, если теорию представления, связанную с функцией, легко понять, но это последнее обычно довольно сложно.

Даже когда вопросы сформулированы в контексте GCT, я понятия не имею , как трудно будет использовать GCT , чтобы доказать (алгебраические аналоги) и т.д. представительские теоретико-домыслы , которые будут возникать в этих контекстах скорее всего, будет иметь вкус, очень похожий на те, что возникают в P против N $FP \neq FEXP$$P$$NP$или постоянный против определителя. Можно надеяться, что классические доказательства этих результатов разделения могут дать некоторое представление о том, как найти теоретико-представительные «препятствия», необходимые для доказательства GCT. Однако доказательства упомянутых вами утверждений - это все теоремы иерархии, основанные на диагонализации, и я не вижу, как диагонализация действительно даст вам глубокое понимание теории представлений, связанной с функцией, которая является полной для (алгебраического аналога) , скажем. С другой стороны, я еще не видел, как сформулировать F E X P в контексте GCT, поэтому пока рано говорить.$FEXP$$FEXP$

$2 \times 2$$\frac{3}{2}n^2 - 2$

$2 \times 2$$3 \times 3$$3 \times 3$$FP \neq FEXP$$P \neq NP$

Есть новая статья об arXiv от Джошуа Грохова , которая показывает, как поместить несколько известных методов нижней границы в структуру GCT, и кажется, что она несколько отвечает на ваш вопрос.

(В основном это просто комментарий, но никто не заметит комментарий, поэтому я публикую его как ответ.)

Объединение и обобщение известных нижних оценок с помощью теории геометрической сложности

Джошуа А. Грохов

$AC^0[p]$посредством чего это естественное объединение и широкое обобщение известных результатов. Это также показывает, что структура GCT, по меньшей мере, столь же мощна, как и известные методы, и дает много новых концептуальных подтверждений того, что GCT действительно может обеспечить значительные асимптотические нижние оценки. Эта новая точка зрения также открывает возможность плодотворного двустороннего взаимодействия между предыдущими результатами и новыми методами GCT; Мы предоставляем несколько конкретных предложений о таких взаимодействиях. Например, теоретико-представительная точка зрения GCT, естественно, предоставляет новые свойства, которые необходимо учитывать при поиске новых нижних границ. Эта новая точка зрения также открывает возможность плодотворного двустороннего взаимодействия между предыдущими результатами и новыми методами GCT; Мы предоставляем несколько конкретных предложений о таких взаимодействиях. Например, теоретико-представительная точка зрения GCT, естественно, предоставляет новые свойства, которые необходимо учитывать при поиске новых нижних границ. Эта новая точка зрения также открывает возможность плодотворного двустороннего взаимодействия между предыдущими результатами и новыми методами GCT; Мы предоставляем несколько конкретных предложений о таких взаимодействиях. Например, теоретико-представительная точка зрения GCT, естественно, предоставляет новые свойства, которые необходимо учитывать при поиске новых нижних границ.