A integridade do coNP implica dureza do NP?

12

A integridade do coNP implica dureza do NP? Em particular, tenho um problema que demonstrei ser coNP-completo. Posso afirmar que é NP-difícil? Percebo que posso reivindicar dureza de coNP, mas não tenho certeza se essa terminologia é padrão.

Estou satisfeito com a afirmação de que, se um problema de NP completo pertencesse ao coNP, então NP = coNP. No entanto, essas notas de aula afirmam que, se um problema NP-difícil pertencer ao coNP, então NP = coNP. Isso sugeriria que não posso afirmar que meu problema é NP-difícil (ou que eu provei coNP = NP, o que duvido muito).

Talvez haja algo errado com o meu pensamento. Meu pensamento é que um problema de coNP-completo é NP-difícil porque:

  1. todo problema no PN pode ser reduzido ao seu complemento, que pertencerá ao coNP.
  2. o problema do complemento no coNP se reduz ao meu problema de coNP completo.
  3. portanto, temos uma redução de todos os problemas no NP para o meu coNP-completo; portanto, meu problema é difícil no NP.
Austin Buchanan
fonte
em uma palavra, não! pelo menos com base no conhecimento atual. a questão está intimamente ligada a P =? NP (ou mais estritamente coNP =? NP, que também está aberta). note que se coNP ≠ NP for comprovado, P ≠ NP também é comprovado porque P é fechado sob complemento.
vzn

Respostas:

10

Você alega que todos os problemas no NP podem ser reduzidos ao seu complemento , e isso é verdade para as reduções de Turing, mas (provavelmente) não para muitas reduções. Uma redução de muitos de para L 2L1L2 é uma função polytime de tal modo que para todos os x , x L 1 sse f ( x ) L 2 .fxxL1f(x)L2

Se algum problema no coNP fosse NP-difícil, então para qualquer idioma M N P haveria uma função politempo f tal que para todos x , x LMNPfx sse f ( x ) L . Como L está no coNP, isso fornece um algoritmo de coNP para M , mostrando que NP coNP e, portanto, NP = coNP. A maioria dos pesquisadores não espera que esse seja o caso e, portanto, os problemas no coNP provavelmente não são difíceis para o NP.xMf(x)LLM=

A razão pela qual usamos reduções de Karp em vez de reduções de Turing é para que possamos distinguir entre problemas difíceis de NP e coNP. Veja esta resposta para obter mais detalhes (as reduções de Turing são chamadas reduções de Cook nessa resposta).

Finalmente, coNP-hard e coNP-complete são terminologia padrão, e você é livre para usá-las.

Yuval Filmus
fonte
"mas não para muitas reduções" - não é o problema de decidir o exatamente que não sabemos se existem reduções de Karp de uma ( co ) NPNP=?coNPcoNP linguagem para seu complemento?
G. Bach
Está correto, e é também isso que mostro na resposta. Quando afirmei que não é verdade para muitas reduções de um, não quis dizer isso no sentido estritamente lógico, mas no sentido de que "a redução na qual você está pensando é uma redução de Turing, mas não uma redução de muitos". .
Yuval Filmus 23/10
Oh tudo bem, sim, esse provavelmente é o problema.
G. Bach
Obrigado. O que é uma boa referência para isso? Em particular para "NP = coNP nas reduções de Cook, mas acredita-se que sejam diferentes reduções de Karp".
Austin Buchanan
A crença de que o PN é diferente do coNP é bastante difundida. Às vezes é atribuído a Stephen Cook. Essa dureza NP é igual à dureza coNP nas reduções de Cook segue imediatamente a definição.
Yuval Filmus
6

O problema com essa linha de raciocínio é o primeiro passo. No caso determinístico, você pode decidir com um TM M se você pode decidir x ¯ L com ele, porque a maneira de fazer isso é apenas virar o bit de saída dexLMxL¯ pois sua saída depende apenas de x (se compare com a definição do verificador de N P ).MxNP

No caso não determinístico usando a definição de verificador, não se sabe se é possível criar um verificador partir de um coNPNPcoNP coNP ou vice-versa, e o problema é que eles têm quantificadores diferentes nas definições que as máquinas verificadoras devem cumprir. Vamos , então temos um verificador DTM M tal que:LcoNPM

xLz{0,1}p(|x|):M(x,z)=1

Para , o verificador M ' terá que cumprirL¯M'

xL¯z{0,1}q(|x|):M'(x,z)=1

Por que não podemos, em seguida, basta usar o -verifier M' da língua K para construir uma coNP -verifier M de K ? O problema é a -quantifier obrigados a ter um coNP -verifier. O NP -verifier M ' pode fornecer 0 para algum certificado (errado), mesmo para x K , portanto você não pode ir de a .NPM'KcoNPMKcoNPNPM'0xK

Talvez de maneira mais abstrata: não está claro como construir (em tempo polinomial) uma máquina que reconheça exatamente os elementos de uma linguagem, independentemente do certificado fornecido, de uma máquina que reconheça exatamente os elementos de uma linguagem que possui algum certificado para mas para os quais também alguns certificados não funcionam.

G. Bach
fonte
4
Surpreendentemente, no entanto, sabe-se que NL = coNL, NPSPACE = coNPSPACE e, em geral, classes não determinísticas definidas por restrições de espaço são fechadas sob complementação. Este é o teorema de Immerman-Szelepcsényi.
Yuval Filmus
Interessante, eu não sabia disso - mas a intuição por trás disso provavelmente é do jeito que sempre acontece com as classes espaciais: podemos simplesmente reutilizar o espaço.
G. Bach
stlognst