É um dos maiores e mais importantes problemas ainda não resolvidos na ciência da computação: é a questão de se a classe computacional P é igual à classe NP ou, se certos problemas para os quais nenhuma solução "rápida" é conhecida podem de fato ser resolvidos "rápido". Isso é importante para algoritmos usados em criptografia. Este problema é de fato tão importante que é um dos sete Problemas do Prêmio do Milênio. Há uma recompensa de um milhão de dólares para resolver este problema.
Acredita-se e às vezes confia-se que P != NP - caso em que P seria um subconjunto adequado de NP = mas uma prova matemática ainda não existe. Se fosse surpreendentemente provado que P = NP, poderia haver consequências práticas para criptografia em que a maioria dos algoritmos depende dos problemas em questão serem difíceis e lentos de resolver - uma prova de P = NP poderia levar a algoritmos rápidos para quebrar a criptografia, mas isso não é uma certeza, apenas um dos cenários possíveis. Qualquer solução para esse problema seria revolucionária e inovadora.
No contexto da complexidade computacional de algoritmos, falamos sobre diferentes tipos de complexidades de tempo de algoritmo, diferentes "velocidades" de algoritmos. Essa "velocidade" não significa o tempo de execução real do algoritmo na vida real, mas sim a rapidez com que o tempo de execução cresce dependendo da quantidade de dados de entrada - então, algo semelhante a "escalabilidade" - estamos interessados apenas na forma da função que descreve como a quantidade de dados de entrada afeta o tempo de execução do algoritmo. Tipos de complexidade de tempo são nomeados após funções matemáticas que crescem tão rapidamente quanto essa dependência, então temos uma complexidade de tempo constante, complexidade de tempo logarítmica, complexidade de tempo linear etc.
Então temos classes de problemas computacionais. Classes dividem problemas com base em quão "rápido" eles podem ser resolvidos.
A classe P significa polinomial e é definida como todos problemas que podem ser resolvidos por um algoritmo executado em uma máquina de Turing determinística com uma complexidade de tempo polinomial.
A classe NP significa polinomial não determinístico e é definida como todos problemas que podem ser resolvidos por um algoritmo executado em uma máquina de Turing não determinística com uma complexidade de tempo polinomial. A definição é a mesma da classe P, com a diferença de que a máquina de Turing é não determinística - tal máquina é mais rápida porque pode fazer uma espécie de "palpites corretos aleatórios" que levam à solução mais rapidamente. Computadores não determinísticos são apenas teóricos, ao menos por enquanto, computadores que temos na vida real não podem executar tais palpites corretos aleatoriamente. Sabe-se que a solução para todos os problemas NP pode ser verificada em tempo polinomial mesmo por uma máquina de Turing determinística, só não sabemos se a solução pode ser encontrada tão rapidamente.
P significa "problemas que podem ser resolvidos rapidamente" e NP significa "problemas cujas soluções podem ser verificadas rapidamente, mas não sabemos se podem ser resolvidas rapidamente".
A questão é se todos problemas NP são de fato problemas P, se todos problemas que podem ser verificados rapidamente também podem ser resolvidos rapidamente. Acredita-se que esse não seja o caso.
Impulsionado por nada. Todo conteúdo é disponível sob CC0 1.0 domínio público. Envie comentários e correções para Mr. Unix em victor_hermian@disroot.org.