Por que as igualdades entre as classes de complexidade se traduzem para cima e não para baixo?

Olá pessoal, entendo que o truque de preenchimento nos permite traduzir classes de complexidade para cima - por exemplo, . O preenchimento funciona "inflando" a entrada, executando a conversão (digamos, de para ), que produz um algoritmo "mágico" que você pode executar na entrada preenchida. Embora isso faça sentido técnico, não consigo ter uma boa intuição de como isso funciona. O que exatamente está acontecendo aqui? Existe uma analogia simples para o que é preenchimento?N P $P=NP \rightarrow EXP=NEXP$$NP$$P$

Pode fornecer uma razão de bom senso por que esse é o caso?

Acho que a melhor maneira de obter intuição para esse problema é pensar em quais são os problemas completos para as classes de tempo exponencial. Por exemplo, os problemas completos para NE são os problemas padrão completos de NP em entradas que podem ser descritas de forma sucinta, por exemplo, dado um circuito que descreve a matriz de adjacência de um gráfico, o gráfico é de 3 cores? Então, o problema de se E = NE se torna equivalente a se os problemas de PN são solucionáveis ​​em tempo polinomial nas entradas descritivamente sucintas, por exemplo, aquelas com pequena complexidade efetiva de Kolmogorov. Obviamente, isso não é mais forte do que saber se eles são solucionáveis ​​em todas as entradas. Quanto maior o tempo limite, menor a complexidade de Kolmogorov das entradas relevantes; portanto, os intervalos de tempo maiores são efetivamente algoritmos que funcionam em subconjuntos menores de entradas.

Russell Impagliazzo

OK, seu objetivo é mostrar que base em (nós não para especificar exatamente o que são essas classes, sabemos que elas são de alguma forma parametrizadas com o tamanho da entrada). Nós temos uma linguagem , decidiu por algum algoritmo . Agora criamos uma linguagem preenchendo cada palavra em , para que seu comprimento seja agora e vemos que ela está contida em (nosso novo algoritmo basicamente apenas ignora os zeros adicionados e executa na entrada curta real).C L A S S 1 [ g ( n ) ] = C L A S S 2 [ h ( n ) ] L ∈ C L $CLASS_1[g(f(n))] = CLASS_2[h(f(n))]$$CLASS_1[g(n)] = CLASS_2[h(n)]$A G ' x ∈ L f ( n ) C G A S S 1 [ g ( n ) ] Uma '$L \in CLASS_1[g(f(n))]$$A$$L'$$x \in L$$f(n)$$CLASS_1[g(n)]$$A'$$A$

O que fazemos é: pegamos uma linguagem da classe maior e a protegemos, para que ela possa ser resolvida por um algoritmo mais fraco, nos dando contenção na classe menor - o algoritmo mais fraco pode fazê-lo, porque possui a mesma quantidade de 'trabalho real' para fazer como antes, mas tem suas restrições (sendo uma função do comprimento da entrada) levantadas estendendo a entrada.

Agora sabemos que e, portanto, (decidido por algum algoritmo ). Gostaríamos de ir daqui para . Mas isso é direto - o algoritmo decide apenas preenche a entrada de acordo e executa na entrada preenchida.L ' ∈ C G A S S 2 [ h ( n ) ] B ' L ∈ C G A S S 2 [ h ( f ( n ) ) ] B L B $L' \in CLASS_1[g(n)]$$L' \in CLASS_2[h(n)]$$B'$$L \in CLASS_2[h(f(n))]$$B$$L$$B'$

Este passo pode ser resumido da seguinte forma: queremos decidir na classe maior e com mais recursos. Usando nossos recursos extras, preenchemos a entrada e executamos o algoritmo que decide a linguagem preenchida$L$ .

É claro que existem alguns detalhes técnicos envolvidos aqui (por exemplo, precisamos garantir que o preenchimento possa ser implementado nas classes que consideramos), mas eu simplesmente as ignoro para fornecer a intuição geral.

Vejo os argumentos de preenchimento em termos de compacidade de representação. Pense em duas máquinas Turing de tradutor: explode instâncias e comprime novamente.$B$$C$

O argumento padding trabalha com , compondo com a versão determinística da MT para o idioma na classe não determinística inferior. As saídas de formam coletivamente uma linguagem que não é representada de maneira compacta, tornando-se "mais fácil".B $B$$B$$B$

Não é possível aplicar a idéia de outra maneira, usando , porque apenas alguns dos idiomas da classe easy são gerados explodindo os idiomas da classe hard.$C$

Para torná-lo mais intuitivo, vamos ver o que está acontecendo de maneira mais abstrata!

Temos duas transformações, uma para entradas e outra para problemas. Vou denotá-las por , ficará claro a partir do contexto quando for a primeira e quando for a segunda.$pad$

Essas duas transformações têm a seguinte propriedade:

I. para todos os problemas , para todas as entradas : x ∈ Σ $A\subseteq \Sigma^{ * }$$x\in\Sigma^{ * }$

$pad(x) \in pad(A)$$x \in A$

$A$$EXP$$NEXP$$pad(A)$$P$$NP$

$EXP$

É claro que as transformações para preenchimento têm essas propriedades.

$EXP$$P$$NEXP$$NP$

Não tenho um argumento formal sobre por que não existem essas transformações no momento, mas intuitivamente o que András Salamon disse estar correto. É fácil aumentar o tamanho das entradas, mas não está claro como elas podem ser compactadas?

$P=NP$$NEXP=NTime(2^{n^{O(1)}})$$x$$n$$N=2^{n^{O(1)}}$

$NEXP(n) = NTime(2^{n^{O(1)}}) = NTime(N) \subseteq NP(N) \subseteq P(N) = Time(N^{O(1)}) = Time(2^{n^{O(1)}}) = EXP(n)$