Problemas fora de P que não são difíceis de P

Ao ler uma resposta de Peter Shor e uma pergunta anterior de Adam Crume , percebi que tenho alguns conceitos errados sobre o que significa ser $\mathsf{P}$ duro.

Um problema é $\mathsf{P}$ difícil se houver algum problema em $\mathsf{P}$ com reduções de $\mathsf{L}$ (ou se você preferir $\mathsf{NC}$ ). Um problema está fora de $\mathsf{P}$ se não existir um algoritmo de tempo polinomial para resolvê-lo. Isso significa que deve haver problemas que estejam fora de $\mathsf{P}$ mas não sejam $\mathsf{P}$ -hard. Se supusermos que FACTORING está fora de $\mathsf{P}$ , a resposta de Peter Shor sugere que FACTORING pode ser um problema.

Existem problemas conhecidos (naturais ou artificiais) que ficam fora de $\mathsf{P}$ mas que não são $\mathsf{P}$ duros? Que tal suposições mais fracas que a suposição de fatoração? Existe um nome para essa classe de complexidade?

cc.complexity-theory complexity-classes Artem Kaznatcheev
fonte

Respostas:

Se $\mathsf{P} \neq \mathsf{L}$ , nenhum conjunto esparso (mesmo um não computável) pode ser $\mathsf{P\text{-}hard}$ .

O equívoco deriva de pensar em classes de complexidade (e problemas computacionais) como criar uma ordem linear que não é verdadeira. Usar a palavra "dureza" para um problema pode ser usado para resolver outros problemas da classe também contribui para o equívoco. Um limite inferior para um problema (por exemplo, não estar em uma classe de complexidade) não implica que o problema seja difícil para a classe (por exemplo, pode ser usado para resolver outros problemas na classe). Não sei se existe uma terminologia alternativa melhor para a "dureza" usada atualmente, uma que foi usada nas décadas anteriores é a "universalidade" (que, IMHO, expressou o conceito com mais fidelidade, e então poderíamos ter usado "dureza" por não estar na classe, mas alterar a terminologia estabelecida é muito difícil).

Kaveh
fonte

alguns dos diagramas de Euler que eu vi de classes de complexidade também alimentaram o segundo equívoco para mim, que é o que acho que causou minha confusão sobre a dureza X.

Artem Kaznatcheev

@ Artigo, sim, isso também é um fator. Aqui está o que eu faço na classe: I mencionar a incomparabilidade de e sob reduções, esperando que isso iria ajudar os alunos a evitar pensar que tudo é linearmente ordenado.

\mod p

$\mod p$

\mod q

$\mod q$

A C^{0}

$\mathsf{AC^0}$

Kaveh

a parte total do pedido com muito menos problemas. Em particular, acho que NP e coNP são bons o suficiente para mostrar que não devemos pensar em classes de complexidade tendo uma ordem total.

Artem Kaznatcheev

Artigo, bom ponto (embora não possamos provar que eles são diferentes). Eu acho que parte do motivo da terminologia é a falta de limites inferiores razoáveis, não temos um bom limite inferior para o SAT, mas achamos que é difícil resolver porque é universal, mas a palavra "universal" não dê a mesma sensação de dificuldade que o "difícil", especialmente para os não especialistas. Mas isso cria o problema porque, embora se possa argumentar que a universalidade de um problema implica que esse problema é difícil de resolver, a dificuldade de resolver um problema não implica que o problema seja universal.

Kaveh

isto é, problemas universais são difíceis (pelo menos tão difíceis quanto qualquer problema da classe), mas problemas difíceis não precisam ser universais.

Kaveh

Eu acho que você pode construir um conjunto não em que não seja -hard por um argumento no estilo Ladner. Aqui está um exemplo específico. $P$ $P$

Em seu artigo "Uma abordagem uniforme para obter conjuntos diagonais em classes de complexidade" (Theor. Comp. Sci. 18, 1982), Schöning prova o seguinte:

Teorema Suponha que , , e são classes de complexidade apresentáveis recursivamente e são fechadas sob variações finitas. Depois, há um conjunto tal que , e se e não for trivial (conjunto vazio ou todas as cadeias), então é polytime, muitos redutíveis a . $A_1 \notin C_1$ $A_2 \notin C_2$ $C_1$ $C_2$ $A$ $A \notin C_1$ $A \notin C_2$ $A_1 \in P$ $A_2$ $A$ $A_2$

Para aplicar este, conjunto para ser o conjunto vazio, e ser -completo sob reduções polytime, definido ser o conjunto de -Hard jogos que estão no , definidos . O conjunto vazio não pode ser -hard (a definição de hardness para um idioma requer que haja pelo menos uma instância no idioma e uma instância que não esteja). definitivamente não está em . O e podem ser verificados para atender às condições acima (semelhante à maneira como Schoening faz para o $A_1$ $A_2$ $EXP$ $C_1$ $P$ $EXP$ $C_2 = P$ $P$ $P$ $A_2$ $C_2$ $C_1$ $C_2$ $NP$ conjuntos completos; veja também esta questão relacionada ). Então temos um que não é um problema -Hard em , e que não está na . Porém, como e não é trivial, é número que pode ser reduzido a um conjunto completo de , portanto está em . Portanto, em particular, também não pode ser duro. $A$ $P$ $EXP$ $A$ $P$ $A_1 \in P$ $A_2$ $A$ $EXP$ $EXP$ $A$ $P$

Na discussão acima, a restrição a problemas -Hard em é necessário para assegurar presentability recursiva, uma vez que os problemas P-disco como um todo são não recursivamente apresentável e nem mesmo contáveis . Agora, exemplos "naturais" disso são uma história diferente ... $P$ $EXP$

Ryan Williams
fonte

Eu gosto de como este atravessa mesmo se . A menos que eu entenda algo errado.

L = P

$L = P$

Artem Kaznatcheev

@ Artigo: Se você considerar a dureza sob redutibilidade do espaço de log, cada idioma não trivial é L-hard. Portanto, se L = P, não há idiomas fora de P são P-hard sob redutibilidade do espaço de log.

Tsuyoshi Ito

Outra maneira de gerar problemas que estão fora de P, mas que não são difíceis de P, é resolver problemas completos para classes incomparáveis com P. Digamos que uma classe X seja incomparável com P, no sentido de que nenhum é um subconjunto da outra. Então, um problema com X completo está necessariamente fora de P (caso contrário, P incluiria X) e não é difícil com P (caso contrário, X incluiria P).

Tentei pensar em algumas classes incomparáveis com P, mas P é uma classe bastante robusta, portanto, não existem muitas dessas classes. Por exemplo, RNC e QNC podem ser incomparáveis com P. DSPACE ( ) também podem ser incomparáveis com P. PolyL é incomparável com P, mas não apresenta problemas completos nas reduções do espaço de log. $\log^2$

Robin Kothari
fonte

Na minha opinião, essa é quase a mesma pergunta formulada de maneira diferente, e não é necessariamente uma maneira de responder à pergunta. De fato, a linguagem A não está nem em P nem em difícil se P e somente se a classe de idiomas redutível a A for incomparável com P (use sua noção favorita de redutibilidade). Quanto à questão atual, acho que é mais provável que seja útil na direção oposta; isto é, é outra maneira de interpretar as respostas para a pergunta atual.

Tsuyoshi Ito