Como sabemos se existe algum problema no NP-completo se não conhecemos todos os problemas no NP?

Um problema é NP-completo se:

1. Está em NP.
2. Todos os problemas no NP podem reduzir a isso.

É o número 2 que me preocupa aqui. Eu ficaria muito surpreso se soubéssemos todos os problemas no NP. Com base nessa premissa, como podemos ter certeza de que algum problema está completo no NP? Por exemplo, como sabemos que não há algum problema que não sabemos que reduzirá ao problema de Satisfação Booleana, mas não ao problema de Clique? Ou esse problema seria NP-Intermediário e, portanto, precisa que P! = NP exista?

Nós não sabemos todos os problemas em NP. Cada problema no NP é dado por uma máquina de Turing não determinística em execução em tempo polinomial. Steve Cook (e, independentemente, Leonid Levin) provou que o SAT é NP-completo , codificando a declaração "A máquina aceita dada opções não determinísticas " como uma fórmula lógica para toda máquina de Turing não determinística; para uma máquina rodando no tempo e no espaço , a codificação tem tamanho aproximadamente ; portanto, quando é tempo polinomial, a codificação tem comprimento polinomial. A fórmula SAT correspondente afirma que "para alguns , a máquina$M$$x$$y$$T$$S$$O(TS)$$M$$y$$M$aceita dado opções não determinísticas ". Esta fórmula é satisfatória se aceita .$x$$y$$M$$x$

Tendo provado que um problema é NP-completo, não há necessidade de fazer essa codificação novamente. Para provar que algum outro problema é NP-hard, é suficiente para reduzir SAT para . Todos os problemas em NP é redutível a sab, e através da redução auxiliar, para . É assim que os resultados da dureza NP são comprovados hoje em dia, reduzindo-se de algum problema de dureza NP.$L$$L$$L$