• Matéria: Informática
  • Autor: rosa66ovgte4
  • Perguntado 5 anos atrás

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")

Respostas

respondido por: ceifadoraa6
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


rosa66ovgte4: Realmente ajudou a entender um bocado, mas eu precisa mesmo era da "Classe Np" (diferente de NP-Completo). Porque sempre que eu pesquiso sobre "lista de problemas da classe np resolvidos", só aparece "Np-Completo", e não "Np" :(
Perguntas similares