Teorema de Ladner Generalizado

O Teorema de Ladner afirma que se P ≠ NP, existe uma hierarquia infinita de classes de complexidade contendo estritamente P e estritamente contidas em NP. A prova usa a integridade do SAT sob várias reduções no NP. A hierarquia contém classes de complexidade construídas por um tipo de diagonalização, cada uma contendo algum idioma para o qual os idiomas das classes mais baixas não são muitos redutíveis.

Isso motiva minha pergunta:

Seja C uma classe de complexidade e D seja uma classe de complexidade que contém estritamente C. Se D contém idiomas que são completos para alguma noção de redução, existe uma hierarquia infinita de classes de complexidade entre C e D, com relação ao redução?

Mais especificamente, gostaria de saber se existem resultados conhecidos para D = P e C = LOGCFL ou C = NC , para uma noção apropriada de redução.

O artigo de Ladner já inclui o Teorema 7 para as classes C com espaço limitado, como Kaveh apontou em uma resposta. Na sua forma mais forte, isso diz: se NL ≠ NP, existe uma sequência infinita de linguagens entre NL e NP, com dureza estritamente crescente. Isso é um pouco mais geral do que a versão usual (Teorema 1), que depende de P ≠ NP. No entanto, o artigo de Ladner considera apenas D = NP.

A resposta para sua pergunta é "sim" para uma grande variedade de classes e reduções, incluindo reduções de espaço de log e as classes mencionadas, como é provado nestes documentos:

H. Vollmer. A técnica da linguagem gap revisitada . Computer Science Logic, Notas de aula em Ciência da Computação vol. 533, páginas 389-399, 1990.

K. Regan e H. Vollmer. Classes de intervalo de idiomas e complexidade de tempo de log . Teórico Computer Science, 188 (1-2): 101-116, 1997.

(Você pode fazer o download dos arquivos postscript compactados desses documentos aqui .)

As provas seguem o princípio básico da extensão de Uwe Schöning ao teorema de Ladner:

Uwe Schöning. Uma abordagem uniforme para obter conjuntos diagonais em classes de complexidade . Teórico Computer Science 18 (1): 95-103, 1982.

A prova de Schöning sempre foi minha prova favorita do teorema de Ladner - é simples e geral.

É muito provável que você possa fazer isso em uma configuração genérica. Quase certamente esse resultado já foi provado em um cenário genérico, mas as referências me escapam no momento. Então, aqui está um argumento do zero.

O artigo em http://oldblog.computationalcomplexity.org/media/ladner.pdf possui duas provas do teorema de Ladner. A segunda prova, de Russell Impagliazzo, produz uma linguagem da forma { x 01 f ( | x | ) } em que x codifica uma fórmula satisfatória ef é uma função computável do tempo polinomial específico. Isto é, simplesmente preenchimento SAT com o número apropriado de 1 's, você pode obter conjuntos de 'NP-intermediários'. O preenchimento é realizado para "diagonalizar" todas as reduções de tempo polinomiais possíveis, de modo que nenhuma redução de tempo polinomial de SAT para L $L_1$$x01^{f(|x|)}$$x$$f$$1$$L_1$funcionará (assumindo ). Para provar que existem infinitos graus de dureza, é possível substituir L 1 no lugar de SAT no argumento acima e repetir o argumento para L 2 = { x 0 1 f ( | x | ) | x ∈ L 1 }. Repita com L i = { x 0 1 f ( | x | ) | x ∈ L i $P \neq NP$$L_1$$L_2 =$$x 0 1^{f(|x|)} | x \in L_1$$L_i =$ }.$x 0 1^{f(|x|)} | x \in L_{i-1}$

Parece claro que essa prova pode ser generalizada para as classes e D , onde (1) C está adequadamente contido em D , (2) D tem uma linguagem completa em reduções em C , (3) a lista de todas as reduções em C pode ser recursivamente enumerados, e (4) a função F é calculável no C . Talvez o único requisito preocupante seja o último, mas se você observar a definição de f no link, parecerá muito fácil calcular, para as classes C mais razoáveis que eu possa pensar.$C$$D$$C$$D$$D$$C$$C$$f$$C$$f$$C$

Penso que a resposta for positiva para e a versão uniforme de N C . A prova de Ladner não usa muito além do que você declarou e o fato de que a classe menor é recursivamente representada e deve funcionar com pequenas modificações, mas eu não verifiquei os detalhes, dê uma olhada no artigo de Lance aqui .$C=L$$NC$

Atualizar

Verifique o artigo de Ladner sobre a estrutura da redutibilidade do tempo polinomial

Aqui está o resumo: Duas noções de redutibilidade de tempo polinomial, denotados aqui por e ≤ P m , foram definidos por Cook e Karp, respectivamente. A propriedade abstrata dessas duas relações no domínio dos conjuntos computáveis ​​é investigada. Ambas as relações provam ser densas e ter pares mínimos. Além disso, existe uma sequência estritamente ascendente com um par mínimo de limites superiores à sequência. Nosso método de mostrar densidade produz o resultado de que, se P ≠ N P , existem membros de N P - P que não são polinomiais completos.$\leq_T^P$$\leq_m^P$$P \neq NP$$NP - P$

Teorema 1. Se B é computado e não em então existe uma calculável Um tal que uma ∉ P , Uma ≤ P m B , e B ≰ P T A .$P$$A$$A \not \in P$$A \leq_m^P B$$B \not \leq_T^P A$

Veja também a seção 6, que discute generalizações:

Teorema 5. Se é uma classe tempo depois ≤ C m e ≤ C T são as relações e teoremas reflexivas e transitórias 1-4 preensão com P substituídos por C .$C$$\leq_m^C$$\leq_T^C$$P$$C$

Teorema 7. Se é uma classe espaço então ≤ C m e ≤ C T são as relações e teoremas reflexivas e transitórias 1-4 preensão com P substituídos por C .$C$$\leq_m^C$$\leq_T^C$$P$$C$

Os termos classe de tempo e classe de espaço são definidos no artigo.

Fiz uma pergunta semelhante a Peter Shor no Mathoverflow aqui . Segundo ele, ele não está ciente de tal resultado.

$NP\neq P$

$A$$\sum_i^p$$B \in \sum_{i-1}^p$$B$

Outro problema interessante é considerar uma generalização de Ladner para as versões prometedoras de classes semânticas, como promessaBPP, promessaMA, etc.