O que é o problema P versus NP? Explicação fácil do problema não resolvido da teoria da complexidade e da diferença entre as classes P e NP

Sobre o 'problema P versus NP', o maior problema não resolvido da ciência da computação, explicamos a sua visão geral de forma clara do ponto de vista de uma máquina de Turing determinística, misturando a diferença entre a 'Classe P', que pode ser resolvida em tempo polinomial, e a 'Classe NP', onde a validade da solução pode ser verificada em tempo polinomial.

Visão Geral

1
A classe P é a classe de problemas que podem ser decididos em tempo polinomial por uma máquina de Turing determinística, e a classe NP é a classe de problemas em que, dada uma evidência (chamada Testemunha) de que a resposta é Sim, a validade da Testemunha pode ser julgada (isso é chamado de verificação) em tempo polinomial. Como os problemas decidíveis em tempo polinomial podem ser verificados em tempo polinomial, é claro que P⊆NP, mas não está claro se P é um subconjunto próprio de NP. Ainda não há prova, mas muitos pesquisadores acreditam que P≠NP. E a conjectura de que esta classe P e a classe NP não são iguais é chamada de "Conjectura P≠NP".

Site de referência : https://daigakudenki.com/np-hard/