P=NP está correto?????????????????????
Soluções para a tarefa
Como assim P=NP? Você está falando sobre o problema do Mileniumm P versus NP?
Quem conseguir provar isso ganhará um prêmio de 1 milhão de doláres.
Acontece que muitos cientistas acreditam que P é diferente de NP.
A principal razão para essa descrença é que após decadas de estudos ninguém foi capaz de encontrar um algoritmo de tempo polinominal para qualquer um dos mais de 3000 importantes conhecidos NP = completos problemas.
Um livro muito bom mesmo para estudar e entender melhor a busca a respeito de N = NP
É este livro aqui:
The Golden Ticket: P, NP, and the Search for the ImpossibleResposta:
Igualmente sem uma resposta está a simples pergunta 'P=NP está correto?'. Na prática, a tarefa pode ser traduzida pela atividade proposta pelo Instituto Clay: você precisa organizar as acomodações de um grupo de 400 estudantes universitários, mas apenas 100 estudantes receberão lugares no dormitório, pois não há espaço para todos. Para complicar, o reitor lhe forneceu uma lista de pares de estudantes que não podem ficar juntos. Diz o regulamento do prêmio do milênio: 'este é um exemplo que os cientistas denominam uma NP-problema, uma vez que é fácil verificar se uma dada escolha de 100 estudantes proposta é satisfatória (isto é, verificar se nenhum par da lista pronta aparece na lista do reitor), porém a tarefa de gerar uma lista desse tipo a partir do zero parece ser tão difícil quanto completamente impraticável'. Ou seja, é possível checar uma lista por uma, mas não se chegou a um cálculo que garanta que o resultado final contemple os dois critérios.
Quem resolver esse problema, afirma Pedro Luiz Aparecido Malagutti, professor do departamento de matemática da Universidade Federal de São Carlos (Ufscar), ganhará muito mais de US$ 1 milhão, já que provavelmente conseguirá quebrar todos os sistemas de segurança dos agentes financeiros mundiais, incluindo os maiores bancos internacionais, já que esses programas são baseados em problemas NP=P