En la teoría de la complejidad computacional , un problema computacional está completo para una clase de complejidad si, en un sentido técnico, se encuentra entre los problemas "más difíciles" (o "más expresivos") de la clase de complejidad.
De manera más formal, un problema p se denomina difícil para una clase de complejidad C bajo un tipo dado de reducción si existe una reducción (del tipo dado) de cualquier problema en C a p . Si un problema es difícil para la clase y para un miembro de la clase, es completo para esa clase (para ese tipo de reducción).
Un problema que es completo para una clase C se dice que es C-completo , y la clase de todos los problemas completos para C se denota C-completo . La primera clase completa que se definió y la más conocida es NP-completo , una clase que contiene muchos problemas difíciles de resolver que surgen en la práctica. De manera similar, un problema difícil para una clase C se llama C-duro , por ejemplo, NP-duro .
Normalmente, se supone que la reducción en cuestión no tiene una complejidad computacional mayor que la de la propia clase. Por lo tanto, se puede decir que si un problema C-completo tiene una solución "computacionalmente fácil", entonces todos los problemas en "C" tienen una solución "fácil".
En general, las clases de complejidad que tienen una enumeración recursiva tienen problemas completos conocidos, mientras que las clases que carecen de una enumeración recursiva no tienen ninguno. Por ejemplo, NP , co-NP , PLS y PPA tienen problemas completos naturales conocidos.
Existen clases sin problemas completos. Por ejemplo, Sipser demostró que existe un lenguaje M tal que BPP M ( BPP con oráculo M ) no tiene problemas completos. [1]