ALogTime! = PH трудно доказать (и неизвестно)?

Лэнс Фортноу недавно заявил, что доказательство L! = NP должно быть проще, чем доказательство P! = NP :

Отдельный NP от логарифмического пространства. Я дал четыре подхода в обзоре диагонализации перед разделом 2001 года (Раздел 3), хотя ни один из них не удался. Должно быть намного проще, чем отделять P от NP.

Раздел 3 в связанном опросе утверждает, что нет значимых результатов разрушения оракула:

В то время как вопрос P! = NP остается весьма сложным, вопрос L! = NP кажется гораздо более решительным. У нас нет оснований считать этот вопрос сложным. Отсутствие хороших релятивизационных моделей для космоса означает, что у нас нет значимой модели оракула, где L и NP разрушаются. Также, поскольку L - однородный класс, ограничения Разборова-Рудича [RR97] не применяются.

На вопрос об известных релятивизационных барьерах для L! = NP на этом сайте был получен ответ, указывающий на то, что полная проблема PSPACE TQBF может использоваться как оракул для получения такого коллапса. Возражение о том, была ли это значимая модель оракула, похоже, тоже получило ответ.

Но даже если бы я понял, почему «у нас нет значимой модели оракула, в которой L и NP разрушаются», следует считать правильным утверждением, у меня все равно остались бы сомнения в том, что доказательство L! = NP более осуществимо, чем доказательство P! = NP. Если доказательство L! = NP действительно должно быть проще, чем доказательство P! = NP, то доказательство ALogTime! = PH должно быть в пределах досягаемости. (В обзорной статье намекает на возможность отделения от ) Я думаю, ALogTime! = PH все еще открыт, и я хотел бы знать, есть ли веские основания ожидать, что это будет трудно доказать. $\Sigma_2^p$ $L$

cc.complexity-theory reductions relativization Томас Климпел
источник

Лэнс Фортнау 7:03, 13 мая 2016 года : «Позвольте мне перефразировать мою точку зрения. Пусть AP будет чередующимся политическим временем (известно, что PSPACE не релятивизирован и, таким образом, отличается от L). Тогда не существует известной модели релятивизации, которая бы делала L = NP для какого-то оракула, но отделяет L от AP для всех оракулов. "

Томас Климпел

Ответы:

$L$ $NP$ $L = NL$ $L^A = NL^A$ $A$

$NC1$ $ALogTime = NP$ $NC1$ $NP$ $NC1$

Кроме того, я не знаю ни одной конкретной причины полагать, что это «трудно доказать», кроме наблюдения, которое пытались многие люди, и никому еще не удалось.

Райан Уильямс
источник

L = N L

$L = NL$

L^{A} = N L^{A}

$L^A = NL^A$

A

$A$

L

$L$

Я полагаю, что в статье, на которую я ссылаюсь, есть подтверждение заявления. Что касается вашего второго предложения: вы спрашиваете, почему Fortnow говорит, что Разборов-Рудич не подходит? Если это так, то он говорит о том, что барьер естественных доказательств, как его обычно понимают, применяется только в том случае, если модель, с которой вы сталкиваетесь, является неоднородной, например, P / poly.

Райан Уильямс

Ах, я неправильно понял: я думал, что барьер, который не применяется, был релятивизацией, а не естественными доказательствами, извините. Я хотел спросить: почему релятивизация является барьером для P против NP, а не L против NL, морально? (Отсюда и несвязанность вопроса.)

Михаэль Кадилхак

Короче говоря, это потому, что модель оракула RST не позволяет вам делать недетерминированные шаги, если лента оракула не пуста. (Причины этого неуловимы; в основном некоторые результаты не будут релятивизированы без него.) Фактический аргумент более сложный ...

Райан Уильямс

Наивная идея для доказательства ALogTime! = PH: проблема значения булевой формулы завершена для ALogTime при детерминированных сокращениях времени регистрации . Следовательно, если ALogTime = PH, то PH = coNP = ALogTime, и, следовательно, проблема значения булевой формулы будет завершена при детерминистическом сокращении времени регистрации для coNP. Следовательно, было бы детерминированное сокращение времени регистрации от задачи тавтологии до проблемы значения булевой формулы.

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

Томас Климпел
источник