Como foram os primeiros problemas NP-completos mostrado ser NP-completo?

Question

A partir da entrada da Wikipedia sobre NP-Completo:

"A maneira mais fácil de provar que algum novo problema é NP-completo é o primeiro a provar que está em NP, em seguida, para reduzir algum problema NP-completo conhecido a ele"

Eu tenho certeza que eu entendo isso: Se eu tiver um problema, eu posso mostrar que é NP-Completo se:

1. mostram que ele está em NP (uma solução para o problema pode ser verificado em tempo polinomial em uma máquina de Turing não determinística)

2. Mostre que um problema já conhecido por ser NP-completos podem ser 'Reduzida' para o novo problema

Então, minha pergunta é, como foram os primeiros problemas NP-completos 'provado' para ser NP-completo? Ao mesmo tempo, o conjunto de conhecidos problemas NP-completos deve ter sido zero, e isso teria tornado impossível recorrer ao passo 2 no processo acima.

Isto faz-me pensar que não há um método diferente para a prova que eu não estou ciente. Ou isso, ou talvez toda a propriedade NP-completo é 'assumido' para determinados problemas devido à falta de uma solução em tempo polinomial conhecido. (Na verdade, ter escrito isso, eu não ficaria surpreso se este for o caso, mas eu gostaria de algum guru-feedback de qualquer forma).

Answer 1

de Cook Teorema

A classe NP pode ser definida como a classe de problemas decidíveis por uma máquina de Turing não determinística em tempo polinomial. mostra Este teorema que SAT é NP-completo codificando a operação de toda a máquina de Turing não-determinístico por uma fórmula booleana, de tal maneira que a máquina aceita se e somente se que a fórmula pode ser satisfeita.

Historicamente falando, a noção de NP-completude foi introduzido em papel seminal de Richard Karp ( Redutibilidade Entre Combinatória problemas ), onde ele definiu NP-completo, utilizado teorema de Cook, e em um tiro grande, mostrou-se 21 problemas NP-completos.

Answer 2

Para dar-lhe a essência da prova (que é várias páginas de difícil ir em Garey & Johnson do Computadores e Intractibility ):

Qualquer problema computacional pode ser expressa como uma máquina de Turing.

É possível expressar a máquina de Turing como um problema de lógica, satisfazendo certas restrições de complexidade.

Portanto, se você pode resolver o problema de lógica em tempo polinomial, você pode resolver o problema da máquina de Turing em tempo polinomial.

Este (junto com algumas outras considerações) mostra que, se você pode resolver o problema de lógica em tempo polinomial, você pode resolver qualquer problema NP em tempo polinomial. Sendo esta a definição de NP-completos, o problema de lógica é, portanto, NP-completo, e pode ser usado como base para outros problemas.

O problema lógica usada é chamada satisfatibilidade (muitas vezes abreviado para SAT). Dada uma série de cláusulas do tipo (A ou não-B ou não-C) (cláusulas constituídos por um número qualquer de proposições e negações de proposições ligados por lógico ou), há uma atribuição de valores de verdade para as proposições que faz com que todos as cláusulas verdade?

NP-completo é uma propriedade bem definido. A única razão que você estaria em dúvida sobre um problema a ser NP-completo é que você pensou que poderia reduzir um outro problema NP-completo a ele, mas não conseguiu encontrar um problema conveniente ou derivar uma prova ainda.

A questão não é se existem problemas NP-completos, ou como ser um problema é NP-completo, mas o que isso significa. Ninguém ainda produziu um algoritmo de tempo polinomial para resolver um problema NP-completo, e ninguém provou que tal algoritmo não pode existir. Seja ou não P = NP, nós certamente não tem bons algoritmos para resolver qualquer problema NP-completo.

Este é um dos problemas Millenium da Fundação Claypool, então se você pode vir até com uma prova que tem sido iludindo algumas pessoas muito brilhantes para muito poucos anos, há um milhão de dólares em-lo para você.