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")
Soluções para a tarefa
Respondido por
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 interessantes
Português,
6 meses atrás
Inglês,
6 meses atrás
Matemática,
6 meses atrás
História,
8 meses atrás
Matemática,
1 ano atrás
Matemática,
1 ano atrás
Matemática,
1 ano atrás