A grandes rasgos, un problema de decisión pertenece a la clase P si podemos encontrar una solución del problema que sea fácil. Un problema de decisión es aquel que podemos contestar con una respuesta de sí o no. La mayoría de los problemas que nos encontramos no son de esta forma, sino que son de optimización. Aún así, si encontramos una solución que sea de decisión, en la mayoría de los casos podemos adaptarla a un problema de optimización.

Un problema de decisión pertenece a NP si la comprobación de la solución es fácil. Uno de los problemas más conocidos que pertenecen a NP, es el “Problema del Agente Viajero”. Lo que nos pregunta es lo siguiente: si un agente de ventas debe visitar n ciudades que están interconectadas, ¿es posible que las visite todas recorriendo una distancia menor a d? Para poder encontrar la solución, debemos realizar una búsqueda exhaustiva entre todas las posibles combinaciones hasta que demos con ella. Pero si ya la tenemos, solamente debemos comprobar que la distancia es menor a d y que pasa por las n ciudades.

Supongamos que cambiamos la pregunta por, ¿es cierto que no puede visitar las n ciudades en una distancia menor a d? Encontrar la respuesta es igual de difícil que la pregunta anterior, sin embargo, comprobar la respuesta no es análogo al problema anterior. Si contamos con la respuesta, aún así debemos realizar todas las comprobaciones para verificar que la respuesta es correcta. Por lo tanto, esta variación de la pregunta ya no es NP.

Dentro de la categoría NP existe la subcategoría NP-completo. Decimos que un problema es NP-completo si pertenece a NP y cualquier otro problema en NP puede ser transformado a este en tiempo polinomial. Para poder decir que un problema es NP-completo, sólo debe ser equivalente a otro y automáticamente lo será a los demás que ya están demostrados. El problema inicial que se usó para hacer la comparación es conocido como "Problema de la Satisfacibilidad Booleana" y mediante el Teorema de Cook sabemos que será equivalente a los demás NP-completo.

Hasta el momento se desconoce si todos los problemas NP pueden ser resueltos en P. Aquí es donde muestran su utilidad los problemas NP-completo, ya que con que se demuestre que uno puede ser resuelto en P, todos los problemas NP también lo serán. Y si se demuestra que un problema NP-completo no puede pasar a P, entonces tampoco los demás NP-completo

Otra categoría es la conocida como NP-difícil, que a pesar del nombre no es una subcategoría de NP. Un problema es considerado NP-difícil si, suponiendo que contamos con alguna forma para resolverlo en tiempo constante, podemos utilizar estas soluciones para resolver un problema NP-completo en tiempo lineal. Por esto, se dice que un problema es NP-difícil si es tanto o más complicado que uno NP-completo, independientemente de si pertenece a NP o no.

Si un problema de optimización tiene una contraparte de decisión que pertenece a NP-completo, entonces este problema de decisión es NP-difícil. Por ejemplo, optimizar el problema del agente viajero (encontrar la menor distancia d para visitar todos los pueblos) es NP-difícil. .