Separações de classes de complexidade sem teoremas de hierarquia

Teoremas da hierarquia são ferramentas fundamentais. Um bom número deles foi coletado em uma pergunta anterior (consulte Quais hierarquias e / ou teoremas de hierarquia você conhece? ). Algumas separações de classes de complexidade seguem diretamente dos teoremas da hierarquia. Exemplos de tais separações bem conhecidos: $L\neq PSPACE$ , $P\neq EXP$ , $NP\neq NEXP$ , $PSPACE\neq EXPSPACE$ .

No entanto, nem toda separação segue um teorema da hierarquia. Um exemplo muito simples é $NP\neq E$ . Mesmo que nós não sabemos se algum deles contém o outro, eles ainda são diferentes, porque $NP$ é fechado com respeito às transformações polinomiais, enquanto $E$ não é.

Quais são algumas separações de classes de complexidade mais profundas, incondicionais e não relativizadas para classes uniformes que não seguem diretamente de algum teorema da hierarquia?

cc.complexity-theory complexity-classes hierarchy-theorems Andras Farago
fonte

Eu acho que é um pouco incomum chamar

N P \neq E

$NP\neq E$ separação. Além disso, a desigualdade é por razões triviais e não nos diz nada de interessante. Todas as separações de classes de complexidade interessantes para grandes classes de complexidade dependem dos teoremas da hierarquia (e na diagonalização) em algum momento.

22414 Kaveh

É verdade que é realmente incomum chamar

separação, como ocorre por razões triviais. Eu o trouxe apenas para mostrar um exemplo simples em que nenhum teorema da hierarquia é necessário.

N P \neq E

$NP\neq E$

Andras Farago 22/02

Err, a prova de NP! = E se depender de um teorema hierarquia! A maneira como funciona é que você primeiro assume NP = E e, em seguida, usa as propriedades de fechamento de NP para deduzir esse E = EXP, violando o Teorema da Hierarquia de Tempo.

Scott Aaronson

Obrigado, Scott, você está perfeitamente certo.

não era o exemplo certo. Eu postei um melhor entre as respostas.

N P \neq E

$NP\neq E$

Andras Farago 27/02

Assim, mesmo essas desigualdades dependem da diagonalização:

mas

E \subseteq N P \subseteq A C^{0} \circ N P \subseteq A C^{0} \circ E \subseteq E X P

$E \subseteq NP \subseteq AC^0\circ NP \subseteq AC^0 \circ E \subseteq EXP$

. Afinal, nada agradável e nada trivial.

E ⊊ E X P

$E \subsetneq EXP$

27414 Kaveh

Respostas:

Eu adoraria ser mostrado errado, mas atualmente não acho que haja limites inferiores uniformes que não sejam baseados em um dos teoremas da hierarquia. Nosso entendimento atual de como tirar proveito da uniformidade é realmente bastante limitado nesse sentido.

Por outro lado, existem muitos limites inferiores uniformes que não seguem diretamente dos teoremas da hierarquia, mas usam um teorema da hierarquia em combinação com outros truques, técnicas e resultados inteligentes, por exemplo:

[Hopcroft-Paul-Valiant]. Eles provam que (a parte não diagonalizada de sua prova) e depois usam o fato de que $\mathsf{CSL} \not\subseteq \mathsf{DTIME}(n)$ $\mathsf{DTIME}(n) \subseteq \mathsf{DSPACE}(n/\log n)$ $\mathsf{CSL} = \mathsf{NSPACE}(n)$ em combinação com a hierarquia de espaço. Seu resultado + a hierarquia espacial também implica . $\mathsf{DSPACE}(n) \nsubseteq \mathsf{DTIME}(n)$
Compromissos de espaço-tempo para Satisfação (veja, por exemplo, as introduções de Buss-Williams e suas referências)
[Paul-Pippinger-Szemeredi-Trotter]. Usa uma simulação não trivial de qualquer máquina de tempo super-linear determinística por uma máquina de quatro alternações mais rápida, em combinação com a hierarquia de tempo determinística. $\mathsf{DTIME}(n) \neq \mathsf{NTIME}(n)$
Limites inferiores uniformes no permanente [ Allender , Allender-Gore , Koiran-Perifel ]
[Williams] (embora tecnicamente esse seja um limite inferior não uniforme, ele usa um monte de idéias inteligentes em combinação com a hierarquia de tempo não determinística) $\mathsf{NEXP} \not\subseteq \mathsf{ACC}^0$

Joshua Grochow
fonte

A separação de Smolensky é algo que você estava procurando? $\mathsf{AC}^0\subsetneq\mathsf{TC}^0$

Arne
fonte

Obrigado, que é um resultado bom, mas eu estou olhando para separações de

classes, não classes de circuito.

u n i f o r m

$uniform$

Andras Farago

@AndresFarago: O uniforme AC ^ 0 também está incluído corretamente no uniforme TC ^ 0.

Emil Jeřábek apoia Monica

@ EmilJeřábek: Existe uma prova de que o uniforme

esteja adequadamente contido no uniforme

que ainda não prova a afirmação não uniforme? (Se não, então parece o seu exemplo cai sob o princípio geral de que limites inferiores não uniformes são mais fortes do que limites inferiores uniformes, e acho que o OQ estava tentando evitar essas respostas ...)

{A C}^{0}

$\mathsf{AC}^0$

{T C}^{0}

$\mathsf{TC}^0$

Joshua Grochow

Penso que a não uniformidade nas provas é secundária ao fato de que são classes bastante pequenas, nas quais temos uma boa compreensão combinatória / algébrica delas. Ou seja, nós os compreendemos bem o suficiente para construir diretamente um objeto que não está neles. Onde existem classes maiores, não existe tal entendimento e, portanto, o único método que conhecemos é fazer a diagonalização contra toda a classe para construir esses objetos.

26414 Kaveh

Outro exemplo não trivial vem da área de complexidade média de casos. Rainer Schuler prova propriedades interessantes da classe que chama de , ver [1]. $P_{P-comp}$

é a classe de idiomas que são aceitos no tempo polinomial em média paracadadistribuição computável em tempo polinomial (p-computável) . Naturalmente, detém, pois a existência de um algoritmo determinista polytime implica que continua a ser eficiente em média, não importa o que a distribuição de entrada é. No entanto, a condição de execução no tempo polinomial médio paracadadistribuição de entrada computávelemP parece forte o suficiente para suspeitar de $P_{P-comp}$ $\mu$ $\mu$ $P\subseteq P_{P-comp}$ . $P_{P-comp}=P$

Surpreendentemente, Schuler prova que existe uma língua , que é Turing completo para , isto é, $L\in P_{P-comp}$ $E$ Isto implica a separação incondicional . Enquanto o último também usa o fato de

E \subseteq P^{P_{P - c o m p}} (*)

$E\subseteq P^{P_{P-comp}}\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; (*)$

P_{P - c o m p} \neq P

$P_{P-comp}\neq P$

, que se segue do Teorema da Hierarquia do Tempo, a parte nova (*) se baseia em diferentes ferramentas: além da diagonalização, emprega medidas limitadas por recursos e complexidade de Kolmogorov.

E \neq P

$E\neq P$

Referência:

[1] R. Schuler, "O fechamento da tabela da verdade e o fechamento de Turing do tempo polinomial médio têm medidas diferentes em EXP", CCC 1996, pdf

Andras Farago
fonte