ALogTime! = PH é difícil de provar (e desconhecido)?

Lance Fortnow afirmou recentemente que provar L! = NP deve ser mais fácil do que provar P! = NP :

Separe NP do espaço logarítmico. Fiz quatro abordagens em uma pesquisa pré-blog de 2001 sobre diagonalização (Seção 3), embora nenhuma tenha sido bem-sucedida. Deve ser muito mais fácil do que separar P de NP.

A Seção 3 da pesquisa vinculada afirma que não há resultados significativos do colapso do oráculo:

Enquanto a pergunta P! = NP permanece bastante formidável, a questão L! = NP parece muito mais tratável. Não temos motivos para pensar que essa pergunta é difícil. A falta de bons modelos de relativização para o espaço significa que não temos um modelo significativo de oráculo onde L e NP entrem em colapso. Também como L é uma classe uniforme, as limitações de Razborov-Rudich [RR97] não se aplicam.

Uma pergunta sobre barreiras de relativização conhecidas para L! = NP neste site obteve uma resposta indicando que o problema completo PSPACE TQBF pode ser usado como oráculo para obter esse colapso. Uma objeção sobre se esse era um modelo de oráculo significativo também parece ser respondida.

Mas, mesmo que eu entenda por que "não temos um modelo significativo de oráculo em que L e NP colapsem" deve ser considerado uma afirmação correta, ainda tenho minhas dúvidas se provar que L! = NP é mais viável do que provar P! = NP. Se provar L! = NP for realmente mais fácil do que provar P! = NP, então provar ALogTime! = PH deve estar definitivamente ao seu alcance. (O artigo da pesquisa sugere a possibilidade de separar de ). Acho que o ALogTime! = PH ainda está aberto e gostaria de saber se existem boas razões para esperar que seja difícil provar. $\Sigma_2^p$ $L$

cc.complexity-theory reductions relativization Thomas Klimpel
fonte

Lance Fortnow 7:03, 13 de maio de 2016 : "Deixe-me reformular meu argumento. Permita que o AP alterne o politimo (conhecido por PSPACE não relativizado e, portanto, diferente de L). Então não há modelo de relativização conhecido que faça L = NP para algum oráculo, mas separa L de AP para todos os oráculos ".

Thomas Klimpel

Respostas:

Não sei por que Fortnow diz que "não há um modelo significativo onde e colapso" ... parece-me que o QBF deve fazê-los entrar em colapso, sob o modelo usual de oráculo Ruzzo-Simon-Tompa (e o link que você incluiu concorda). Observe que este modelo de oráculo também tem suas peculiaridades: temos se e somente se para cada oráculo , portanto, qualquer oráculo testemunhando uma separação implicaria a separação não relativizada. $L$ $NP$ $L = NL$ $L^A = NL^A$ $A$

ALogTime = LOGTIME-Uniforme . Então, sim, está aberto. Há uma noção relativizada de uniforme , e você pode recolher e nessa noção. Veja o Teorema 6 em http://link.springer.com/article/10.1007/BF01692056 . (Uma ressalva: tecnicamente falando, esse artigo considera o NC1 uniforme do LOGSPACE, mas acredito que uma versão razoável dessa construção do oráculo deve funcionar na configuração uniforme do LOGTIME.) $NC1$ $ALogTime = NP$ $NC1$ $NP$ $NC1$

Além disso, não conheço nenhuma razão específica para acreditar que seja "difícil de provar", exceto a observação de que muitas pessoas tentaram e nenhuma ainda conseguiu.

Ryan Williams
fonte

L = N L

$L = NL$

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

$L^A = NL^A$

A

$A$

L

$L$

Acredito que exista uma prova da declaração no artigo que vinculei. Em relação à sua segunda frase: você está perguntando por que Fortnow diz que Razborov-Rudich não se aplica? Nesse caso, o argumento dele é que a barreira de provas naturais, como geralmente entendida, só se aplica se o modelo com o qual você é mais limitado não é uniforme, por exemplo, P / poli.

Ryan Williams

Ah, eu interpretei errado: pensei que a barreira que não se aplicava era a relativização, não as provas naturais, desculpe. O que eu queria perguntar era: por que a relativização é uma barreira moral para P vs NP, mas não para L vs NL? (Daí a falta de relação com a questão.)

Michaël Cadilhac

Em resumo, é porque o modelo RST oracle não permite que você faça etapas não determinísticas, a menos que a fita oracle esteja em branco. (As razões para isso são sutis; basicamente, alguns resultados não relativizar sem ele.) O argumento real é mais complicado ...

Ryan Williams

Uma idéia ingênua para provar ALogTime! = PH: O problema do valor da fórmula booleana está completo para ALogTime sob reduções determinísticas de tempo de log . Portanto, se ALogTime = PH, PH = coNP = ALogTime e, portanto, o problema do valor da fórmula booleana estaria completo sob reduções determinísticas de tempo de log para coNP. Portanto, haveria uma redução determinística do tempo do log do problema de tautologia para o problema de valor da fórmula booleana.

As reduções determinísticas do tempo de log devem ser inofensivas, elas não podem contribuir muito para a solução do problema de tautologia. Eles são apenas uma boa formalização, o que significa que uma redução só pode funcionar muito localmente. Portanto, a tarefa restante é entender por que o problema de tautologia não pode ser transformado em um problema de valor de fórmula booleana por reduções muito locais. Ainda não vejo como fazer isso, mas pelo menos a tarefa restante é muito clara, para que eu tenha pelo menos uma chance de entender por que é difícil (ou não).

Thomas Klimpel
fonte