A questão P versus NP é um dos problemas mais fundamentais da ciência da computação. Ela pergunta se todo problema cuja solução pode ser verificada rapidamente (classe NP) também pode ser resolvido rapidamente (classe P). Em outras palavras, se existe um algoritmo eficiente que pode resolver todos os problemas que podem ser verificados em tempo polinomial. Se P for igual a NP (P = NP), isso significaria que problemas complexos, como a fatoração de números grandes ou o problema do caixeiro viajante, poderiam ser resolvidos rapidamente, o que teria enormes implicações em áreas como criptografia, otimização e inteligência artificial. Por outro lado, se P for diferente de NP (P ≠ NP), isso confirmaria que existem problemas que, embora suas soluções possam ser verificadas rapidamente, não podem ser resolvidos rapidamente. Esse é um tema central na teoria da computação e ainda não foi resolvido, sendo um dos sete Problemas do Prêmio Millenium, com uma recompensa de um milhão de dólares para uma solução.