En la teoría de la complejidad computacional , un problema computacional es completo para una clase de complejidad si se encuentra, en un sentido técnico, entre los problemas "más difíciles" (o "más expresivos") de la clase de complejidad.
Más formalmente, un problema p se llama difícil para una clase de complejidad C bajo un tipo de reducción dado si existe una reducción (del tipo dado) de cualquier problema en C a p . Si un problema es difícil tanto para la clase como para un miembro de la clase, está completo para esa clase (para ese tipo de reducción).
Un problema que está completo para una clase C se dice que es C-completo , y la clase de todos los problemas completos para C se denota como C-completo . La primera clase completa que se define y la más conocida es NP-complete , 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 mayor complejidad computacional que la propia clase. Por lo tanto, se puede decir que si un problema de C completo tiene una solución "computacionalmente fácil", entonces todos los problemas en "C" tienen una solución "fácil".
Generalmente, las clases de complejidad que tienen una enumeración recursiva han conocido problemas completos, mientras que las clases que carecen de una enumeración recursiva no tienen ninguno. Por ejemplo, NP , co-NP , PLS y PPA tienen problemas naturales completos conocidos.
Hay clases sin problemas completos. Por ejemplo, Sipser demostró que existe un lenguaje M tal que BPP M ( BPP con Oracle M ) no tiene problemas completos. [1]