Ainda tratando do problema SAT, considere o seguinte: (a) é sabido que 3-SAT está na classe NP-Completo; (b) é fácil provar que k-SAT alfa x-SAT se x=k-1 (c) é facil prvar que 2-SAT está na classe P. Explique porque esses argumentos não são admitidos como prova para P=NP
Pergunta
bebetoss
Ainda tratando do problema SAT, considere o seguinte: (a) é sabido que 3-SAT está na classe NP-Completo; (b) é fácil provar que k-SAT alfa x-SAT se x=k-1 (c) é facil prvar que 2-SAT está na classe P. Explique porque esses argumentos não são admitidos como prova para P=NP
Link para o comentário
Compartilhar em outros sites
0 respostass a esta questão
Posts Recomendados
Participe da discussão
Você pode postar agora e se registrar depois. Se você já tem uma conta, acesse agora para postar com sua conta.