A partir desse ponto, é preciso restringir ligeiramente nossa atenção aos problemas que são razoáveis no seguinte sentido:  é fácil reconhecer uma solução de uma instância do problema quando se está diante de uma.  (É difícil imaginar um problema que não tenha essa propriedade… ) 

Mais precisamente, um problema X é polinomialmente verificável se é possível verificar, em tempo polinomial, se uma suposta solução de uma instância de X é de fato uma solução, ou seja, se existe um algoritmo que, ao receber uma instância I de X e uma suposta solução S de I, responde sim ou não conforme S seja ou não solução de I,  e  consome tempo limitado por um polinômio no tamanho de I para responder sim.  (Segue daí, em particular, que as soluções são curtas, ou seja, o tamanho de uma solução é polinomial no tamanho da instância.)

           O conjunto dos problemas polinomialmente verificáveis constitui a classe NP de problemas.  (Cuidado!  NP não é abreviatura de não polinomial mas sim de nondeterministic polynomial.) 

(A bem da verdade, essa definição da classe NP é tecnicamente incorreta, pois deveria ser aplicada somente a problemas de decisão, ou seja, problemas que só admitem as soluções sim e não.  A rigor, deveríamos escrever FNP no lugar de NP.)

           Todos os problemas na primeira das duas listas de exemplos acima pertencem à classe NP.  Segue a discussão de alguns desses exemplos:

Equação do segundo grau:  É fácil verificar se um dado inteiro x satisfaz a equação ax² + bx + c = 0:  basta calcular o número a × x × x + b × x + c e compará-lo com zero.  Se x satisfaz a equação então o número de dígitos de x não passa do número de dígitos de (a, b, c) e portanto os cálculos consomem tempo limitado por um polinômio nos números de dígitos de (a, b, c).  Portanto, o problema da equação do segundo grau pertence à classe NP.

            Fatoração: É fácil verificar se um dado número natural p é divisor de n:  basta dividir n por p usando o algoritmo de divisão que todos aprendemos na escola.  Se p divide n então p ≤ n e portanto os cálculos consomem tempo polinomial no número de dígitos de n.  Assim, o problema da fatoração está na classe NP.

           O problema do ciclo longo está na classe NP pois é possível verificar em tempo polinomial se uma dada sequência de vértices é um ciclo do grafo e tem comprimento maior que k.

           O problema do ciclo hamiltoniano está em NP pois é possível verificar em tempo polinomial se uma dada permutação dos vértices é um ciclo do grafo.

           O problema do campo minado está em NP pois é possível verificar em tempo polinomial se uma dada distribuição das minas é consistente com a configuração dada.

              Não é fácil dar bons exemplos de problemas que não estejam na classe NP.  Um exemplo bobo é o problema de construir uma lista de todos os subconjuntos de {1, 2, …, n} uma vez dado n. Um exemplo melhor é o roadblock problem.

Suspeita-se que muitos problemas de otimização não estão na classe NP. No caso do problema do ciclo máximo, por exemplo, embora seja fácil verificar se uma dada sequência de vértices é um ciclo, não se conhece uma maneira eficiente de verificar que o ciclo é máximo.  (No entanto, o problema do máximo divisor comum está em NP pois está em P, como mostra o algoritmo de Euclides.)