Completo (complejidad)

En la teoría de la complejidad computacional , un problema computacional es 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 dicha clase.

De forma más formal, un problema p se considera 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 para la clase y pertenece a ella, es completo para esa clase (para ese tipo de reducción).

Un problema que es completo para una clase C se denomina C-completo , y la clase de todos los problemas completos para C se denota como C-completa . La primera clase completa que se definió y la más conocida es NP-completa , 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 denomina C-difícil , por ejemplo, NP-difícil .

Normalmente, se asume que la reducción en cuestión no tiene una complejidad computacional mayor que la de la clase misma. 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 poseen una enumeración computable tienen problemas completos conocidos, mientras que las clases que carecen de ella no los tienen. Por ejemplo, NP , co-NP , PLS y PPA tienen problemas completos naturales conocidos.

Hay 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 ]}