En la teoría de la complejidad computacional , un problema computacional está 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 denomina duro 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, 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 C-completo . La primera clase completa por definir 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 denomina C-difícil , por ejemplo, NP-difícil .
Normalmente, se asume 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 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 tienen problemas completos conocidos, mientras que las clases que carecen de una enumeración recursiva no tienen ninguno. Por ejemplo, NP , co-NP , PLS , PPA tienen problemas completos naturales conocidos, mientras que RP , ZPP , BPP y TFNP no tienen problemas completos conocidos (aunque tal problema puede descubrirse en el futuro). [ cita requerida ]
Hay clases sin problemas completos. Por ejemplo, Sipser mostró que hay un lenguaje M tal que BPP M ( BPP con Oracle M ) no tiene problemas completos. [1]
Referencias
- ^ Sipser, Michael (1982). "Sobre la relativización y la existencia de conjuntos completos". Autómatas, lenguajes y programación . Apuntes de conferencias en Ciencias de la Computación. 140 . págs. 523–531. doi : 10.1007 / BFb0012797 . ISBN 978-3-540-11576-2.