La clase NP ta compuesta polos problemes que tienen un certificáu sucinto (tamién llamáu testigu polinómico) para toles instancies que la so respuesta ye un SÍ. La única forma de que tengan un tiempu polinomial ye realizando una etapa aleatoria, incluyendo lazar de dalguna manera pa escoyer una posible solución, y entós netapes posteriores comprueba si esa solución ye correuta.