Question

Alguém consegue me ajudar com 3 exemplos passo a passo (como resolver) da Classe NP?
Eu estou procurando no Google, mas só aparece "Np-Completo" (que não é o que eu preciso) e Np-Difícil (que eu não sei se se encaixa no que eu preciso, já que é só "P, Np e Np-Completo")

Answer 1

Resposta:

Um problema NP-Completo é um problema pertencente à classe de problemas NP que pode ser reduzido em tempo polinomial ao problema da satisfatibilidade booleana (SAT):

Dada uma expressão booleana expressa como uma conjunção de disjunções entre n variáveis, negadas ou não, como por exemplo:

(x1 ou x2 ou não x3 ou x4) e (x1 ou não x2 ou x3 ou não x4) e ...

Encontrar um conjunto de valores para x1, x2, x3, ... xn tal que essa expressão seja verdadeira.

Explicação:

Acho q dá pra entender um pouco, e espero ter ajudado