Como provar que um problema NÃO é NP-Completo?

Existe alguma técnica geral para provar que um problema NÃO é NP-Completo?

Eu recebi esta pergunta no exame que me pediu para mostrar se algum problema (veja abaixo) é NP-Complete. Eu não conseguia pensar em nenhuma solução real e apenas provei que estava em P. Obviamente, essa não é uma resposta real.

NP-Complete é definido como o conjunto de problemas que estão no NP e todos os problemas do NP podem ser reduzidos a ele. Portanto, qualquer prova deve contradizer pelo menos uma dessas duas condições. Esse problema específico está de fato em P (e, portanto, em NP). Então, eu estou preso em provar que há algum problema no NP que não pode ser reduzido a esse problema. Como diabos isso pode ser provado?

Aqui está o problema específico que recebi no exame:

Seja o conjunto de seqüências de caracteres na forma normal disjuntiva . Seja D N F S A T o idioma das seqüências de caracteres de D N F que são satisfatórias por alguma atribuição de variáveis. Mostrar se D N F S A T está ou não em NP-Complete.$DNF$$DNFSAT$$DNF$$DNFSAT$

Com base nos comentários, você parece querer uma resposta incondicional.

No entanto, o DNF-SAT está em L, atribuindo variáveis ​​para satisfazer o primeiro disjuntor. Portanto, se estiver completo com NP, então L = NP.

Por outro lado, se L = NP, DNF-SAT é NP-completo sob reduções de espaço de log, trivialmente. (De fato, se L = NP, todo problema no NP é NP-completo sob reduções do espaço de log.)

Segue-se que L = NP se DNF-SAT é NP-completo sob reduções de espaço de log.

Portanto, no momento, você não pode fazer uma declaração incondicional de que o DNF-SAT não é NP-completo, como você deseja fazer. Não é necessário assumir P ≠ NP, mas a resposta precisa estar condicionada a algo, e L ≠ NP é a hipótese mais fraca possível que garante o resultado desejado.

Um problema é NP-completo se é tanto NP- difíceis e em NP. Isso significa que você precisa refutar um desses dois.$Q$

1. Sob a suposição de que P $\neq$ NP, você pode dar um tempo polinomial algoritmo de resolução de . Mais raramente, sob a suposição de que o isomorfismo do gráfico não é NP-rígido, você pode mostrar que Q é politmo redutível ao gráfico do isomorfismo.$Q$$Q$
2. Você mostra isso não está no NP. Isso é mais difícil e você geralmente deve usar outras suposições, como o não colapso da hierarquia polinomial, que NP ≠ coNP ou mostre que é difícil para alguma outra classe superior a NP, por exemplo, mostrando que é NEXPTIME-difícil.$Q$$\neq$

Normalmente, a resposta é fornecer um algoritmo de tempo polinomial, que seria o mais simples para DNF-SAT, mas isso depende da hipótese de que P NP. No entanto, provar que DNF-SAT não é NP-completo sem nenhuma suposição implica, como Shaull aponta, provar que P ≠ NP, de modo que é um pouco mais complicado.$\neq$$\neq$

Pela hierarquia de tempo não determinística, você pode mostrar que o problema é -hard; como N P ≠ N E X P , é impossível reduzir o problema em tempo polinomial a qualquer problema em N P , para que o problema não esteja em$\mathsf {NEXP}$$\mathsf {NP} \ne \mathsf {NEXP}$$\mathsf {NP}$ .$\mathsf {NP}$

No entanto, se o seu problema não for tão difícil, você pode ser pressionado a provar que não está em ; e se estiver em N P , você será pressionado a mostrar que N P não é redutor de Karp para o seu problema sem assumir que P ≠ N $\mathsf {NP}$ $\mathsf {NP}$$\mathsf {NP}$$\mathsf P \ne \mathsf {NP}$ .

Como é o caso de todas as provas, não existe uma fórmula para provar uma afirmação, você precisa adivinhar, tentar e errar e esperamos poder provar o que está tentando provar. Para provar que um problema NÃO é NP-Completo, negue a definição (Lei DeMorgran), ou seja, prove o problema NÃO no NP ou prove o problema NÃO no NP-Difícil.

Acredito que o que o palestrante realmente quer é que você possa distinguir problemas que estão em P dos problemas que são NP-completos no significado dado a linguagem, você pode construir um algoritmo eficiente? se sim, suspeita-se que não seja NP-completo porque não achamos que os idiomas em P sejam NP-completos! caso contrário, você ainda precisará provar que o problema é difícil para o NP!

note que existem alguns problemas que não conhecemos, como status de isomorfismo de gráfico, fatoração de número determinado, ... achamos que esses problemas não são NP-completos, mas ninguém poderia provar isso! especificamente, temos evidências de que o isomorfismo do gráfico não é NP-completo! Outro problema é a conjuntura de jogo única que suspeitamos que o jogo único seja NP-completo, mas não existe prova! portanto, a abordagem que você descreve não é útil!