verificar é mais fácil do que encontrar?
encontrar uma solução para um problema deve ser mais difícil do que verificar se uma solução está correta. Isso parece óbvio Se você já resolveu um quebra-cabeça sudoku, ou resolveu um cubo de Rubik, ou jogou um jogo de xadrez. Mas essa afirmação, por mais intuitiva que seja, nos leva diretamente a uma das questões matemáticas mais profundas colocadas pela nossa civilização.
tempo polinomial não-determinístico (ou NP) problemas são aqueles em que você pode facilmente verificar uma resposta para estar correto., Em contraste, os problemas de tempo polinomial (ou P) são aqueles em que encontrar a resposta é fácil. Se você pode encontrar a resposta, então você verificou para ser correto, então todo problema em P também está em NP. Dizemos que P é uma subclasse de NP. No entanto, não sabemos se há algum problema particular em NP que não está em P, e isso é o que chamamos de problema P vs NP.
O problema P vs NP é um dos problemas mais centrais não resolvidos em matemática e Ciência da Computação Teórica. Há até um prémio Clay Millennium que oferece um milhão de dólares pela sua solução., No entanto, há maneiras muito mais fáceis de se tornar um milionário do que resolver P vs NP!
houve um zumbido recentemente quando alguém propôs resolvê-lo em arXiv, embora uma lacuna na prova foi rapidamente encontrada. Dado o interesse recente no problema e seu lugar central na matemática, eu discuto isso no blog desta semana.
Sudoku
Se lhe for dado um ‘Sudoku’ preenchido num jornal, poderá jogá-lo no caixote do lixo. Mas se você quiser, você pode digitalizar através das linhas, colunas, e 3 x 3 células para dizer que é uma solução válida: cada uma de 1, 2, … , 9 deve ocorrer exatamente uma vez., Isso é análogo ao NP, pois é relativamente fácil verificar se uma solução está correta.
no entanto, se eu lhe der um Sudoku parcialmente preenchido, pode ser difícil encontrar a solução. É a alegria e o desafio deste tipo de puzzle. Então estar em NP não parece imediatamente implicar que o problema tem uma solução fácil de encontrar. Essa intuição está no centro do problema P vs NP.
formulação precisa
para entender P e NP com mais precisão, precisamos entender melhor os algoritmos e medir sua velocidade. Problemas são colocados com algumas entradas e Saídas fixas ou SIM ou não. A entrada é um dado comprimento, digamos n, onde n é um inteiro positivo. Isto representa o número de bits necessários para expressar a entrada. Um algoritmo é um método ou procedimento para resolver um problema. Algoritmos fornecem instruções em cada passo de um cálculo e devem terminar., Os passos podem ser segundos, milisegundos, ou algum outro intervalo fixo de tempo que depende do seu problema.
a complexidade de um problema é o tempo mínimo de execução do pior caso em todos os algoritmos possíveis resolvendo o problema em função do comprimento da entrada. Em outras palavras, ele mede quanto tempo leva para resolver o problema com o algoritmo mais rápido, mas com a entrada do pior caso.
um problema é solucionável em tempo polinomial se dada uma entrada de comprimento n, sua complexidade é limitada acima pela função polinomial nm para algum inteiro não-negativo M., O conjunto de todos os problemas solúveis em tempo polinomial é denotado por P.
estar em P não significa necessariamente que o problema é viável. Por exemplo, se tomar n1000 passos para executar o algoritmo, então ele será irremediavelmente lento mesmo para pequenos problemas polinomiais não-determinísticos (ou NP) são aqueles onde você pode verificar se a resposta sim é correta em tempo polinomial.
NP-dureza
Um problema é NP–difícil se um algoritmo em tempo polinomial para que implicaria um algoritmo em tempo polinomial para cada problema em NP. Portanto, se um problema NP-difícil estava em P, então P = NP., Os problemas NP-hard são pelo menos tão difíceis quanto qualquer problema em NP. Um problema NP–completo é um que é NP-difícil e em NP.
um problema clássico NP-completo é encontrar um ciclo Hamilton. Para isso, suponhamos que temos uma rede de cidades conectadas por estradas. O problema é visitar cada cidade usando estradas (não são permitidos aviões!) and come back to the start. Isto parece fácil para um pequeno número de cidades, mas se você recebeu centenas delas, então torna-se difícil., Milhares de outros problemas NP-completos são conhecidos surgindo na teoria dos grafos, teoria dos números, geometria e outras áreas da matemática e Ciência da computação.qual é a resposta, a sério?
Se eu fosse apostar, então eu assumiria que P não é igual a NP, e eu acho que a maioria dos especialistas concordaria. Teríamos que ser terrivelmente burros para não ver como todos os milhares de problemas NP-completos não têm um algoritmo de tempo polinomial. Mas como espécie, mudo é a nossa posição padrão para que ninguém possa dizer qual é a resposta com 100% de certeza.,
O que é interessante sobre o problema P vs NP é que ele aponta para o quão limitada nossa compreensão é em provar que certos problemas não têm soluções rápidas. Isto é parte de um tema maior no campo da teoria da complexidade computacional, que estuda dezenas de outras classes de complexidade. Confira o jardim zoológico de complexidade para uma lista dessas classes. Para a maior parte, é aberto para mostrar várias classes de complexidade (frequentemente de som exótico) são subclasses próprias um do outro. Por exemplo, não se sabe se NL é uma subclasse adequada de P, e não sabemos se FPT é uma subclasse adequada de W.,
independentemente da sua veracidade, é provável que o problema P vs NP permaneça aberto por algum tempo. A menos que seja provado que P = NP, Sudoku permanece seguro.Anthony Bonato