Eu não sei porque eu vou falar sobre isso, mas eu vou, to nem ligando. Esse é um dos problemas mais atuais da matemática e é extremamente conhecido por ter suas bases na computação. Tem gente tentando descobrir a resposta até hoje, e apesar da quantidade de esperança envolvida, a resposta provavelmnte é negativa.
Qual seria a pergunta que assola os pesquisadores pelo mundo afora? Bom, o que eu posso dizer é que ela com certeza livraria muita gente da computação de um peso de dúvida desnecessário. Então liga o seu javascript aí que aí vem textinho.
Pois é. Parece simples. O problema é que a gente não sabe se essa igualdade é verdadeira ou falsa. O que eu estou colocando ali não é interpretado como uma afirmação. Não se sabe se "P" de fato é igual a "NP", e pra falar a verdade essa expressão fica completamente sem sentido se você não especificar exatamente o que é P e o que é NP.
Bom. P são algoritmos cujo tempo de processamento máximo cresce de acordo com o tamanho da entrada como uma função polinomial em uma Máquina de Turing Determinística. Note bem essa palavra destacada, ela significa computador, ou pelo menos a definição formal de computador que é aceita até hoje.
Vou repetir. Máquina de Turing Determinística. Agora você deve lembrar.
E NP? Bom, isso significa que o tempo de processamento máximo cresce de acordo com o tamanho da entrada como uma função pelo menos exponencial em uma Máquina de Turing Determinística. Ou seja, demora pra cacete pro algoritmo terminar.
Ok. Isso não faz muito sentido porque um tipo de algoritmo certamente é diferente do outro, mas a pergunta, por mais que seja ilustrada grosseiramente daquela forma quer dizer o seguinte: Dado um problema com um determinado input onde uma solução pode ser verificada em tempo polinomial, existe um algoritmo capaz dee encontrar uma solução qualquer em tempo também polinomial?
Um dos problemas clássicos é o agendamento de veículos. Suponha que você tem um conjunto de veículos com produtos, e cada produto deve ser entregue em uma determinada cidade. Qual é o melhor agendamento que você pode fazer para eles? Vamos definir alguns conjuntos. V é o conjunto de veículos, C de cidades. Vamos supor que você pode sempre se deslocar de uma cidade para outra cidade mas você tem uma distância associada.
E entre essas cidades podemos montar a matriz D de distâncias mapeando a distância de uma cidade a outra.
Obviamente
Agora se eu te der dois agendamentos possíveis, você consegue compará-los facilmente, mas, dentre todos os possíveis, qual é o melhor agendamento?
Começou a sentir o problema? Lembre-se que ele é um dos problemas do milênio e solucioná-lo te dá 1 milhão de dólares!
E aí, você acha que P = NP ou que P != NP?
Eu acho que P não é igual a NP.
ResponderExcluirPorque P é P. E NP é NP.
P pode até ser bem próximo de NP. Tão próximo talvez que seja irrelevante ou impossível de se averiguar.
Agora, pra mim não faz diferença algum o P, o NP, ou a PQP, se você não me disser o que são funções polinomiais, funções pelo menos exponenciais, e o que a diferença na prática das duas interfere no tempo de processamento máximo de acordo com o tamanho da entrada num caralho de uma Máquina de Turing Determinística, vulgo, a porra de computador.