Co-NP-completo

Co-NP-completo

En teoría de la complejidad computacional, la clase de complejidad co-NP-completo es el conjunto de los problemas de decisión más difíciles de la clase co-NP, en el sentido que son los que menos parecen pertenecer a la clase de complejidad P. De encontrarse una forma de resolver un problema en co-NP-completo en tiempo polinómico, el algoritmo utilizado serviría para resolver todos los problemas de co-NP con la misma complejidad.

Más precisamente, un problema de decisión C pertenece a co-NP-completo si está en co-NP y si todo problema de co-NP tiene una transformación polinómica hacia él. Esto significa que para todo problema L en co-NP, existe un algoritmo que trabaja en tiempo polinómico que puede transformar una instancia de L en una instancia de C con el mismo resultado. Consecuentemente, de tenerse un algoritmo que trabajase en tiempo polinómico para C, se tendría un algoritmo en tiempo polinómico para cada uno de los problemas de co-NP.

Cada problema en co-NP-completo es el complemento de uno en NP-completo. Los dos conjuntos son o iguales o disjuntos. Se supone que es lo último lo que es cierto, pero no se ha demostrado.


Wikimedia foundation. 2010.

Игры ⚽ Нужна курсовая?

Mira otros diccionarios:

  • completo — completo, ta adjetivo 1. (estar) Que tiene todas las partes que lo componen: La colección está completa. 2. (antepuesto / pospuesto) Que es total en todos sus aspectos: La fiesta ha sido un completo fracaso. La victoria ha sido completa. Sinónimo …   Diccionario Salamanca de la Lengua Española

  • completo — completo, ta adjetivo 1 entero*, íntegro, cabal, acabado, perfecto, lleno, cumplido, exacto. Íntegro equivale a entero; cabal reúne los matices de completo y entero. Cuando se trata de un trabajo u obra terminados, decimos que están completos,… …   Diccionario de sinónimos y antónimos

  • completo — completo, ta (Del lat. complētus, part. pas. de complēre, terminar, completar). 1. adj. Lleno, cabal. 2. Acabado, perfecto. por completo. loc. adv. completamente. ☛ V. dentición completo, flor completo, pensión completo …   Diccionario de la lengua española

  • completo — /kom plɛto/ [dal lat. completus, part. pass. di complēre compiere ; come s.m., nel sign. 2, dal fr. complet ]. ■ agg. 1. a. [che ha tutte le sue parti] ▶◀ compiuto, definitivo, finito, intero, perfetto, sano. ◀▶ imperfetto, incompiuto, incompleto …   Enciclopedia Italiana

  • Completo — puede referirse a: Algo íntegro, lleno, pleno, cumplido, acabado, perfecto. Espacio completo, en matemáticas. Completo, sándwich típico chileno, similar al hot dog. Véase también Completas, la última oración de la liturgia de las Horas… …   Wikipedia Español

  • completo — |é| adj. 1. A que não falta nada. 2. Que tem todas as qualidades exigidas. 3. Perfeito. 4. Que não admite mais, cheio. 5. Cabal; satisfeito. 6. Total; pleno. • s. m. 7. Estado do que se acha completo …   Dicionário da Língua Portuguesa

  • completo — (Del lat. completus, lleno.) ► adjetivo 1 Que tiene todos los elementos o partes que normalmente lo componen: ■ me han regalado una cubertería completa. SINÓNIMO entero íntegro ANTÓNIMO incompleto 2 Que está lleno: ■ la sala está completa …   Enciclopedia Universal

  • Completo (gastronomía) — Un completo italiano siendo degustado. El completo es un sándwich que corresponde a una variación chilena del perrito caliente. Consiste en un pan alargado con una salchicha en el medio, acompañada de distintos ingredientes. Es el sándwich más… …   Wikipedia Español

  • completo — com·plè·to agg., s.m. FO I. agg. I 1. di qcs., che ha tutti gli elementi che deve o può avere: un elenco, un resoconto completo; aspirapolvere completo di accessori; opera completa di un autore, edizione che comprende tutti i suoi scritti; avere… …   Dizionario italiano

  • Completo — Chilean Completo A completo italiano Origin Place of origin Chile Dish details …   Wikipedia

  • completo — adj 1 Que tiene todas sus partes o elementos, que contiene todo lo que debe contener: un aparato completo, cupo completo 2 Que está terminado o que ha alcanzado su carácter definitivo: una obra completa, un éxito completo, un completo acuerdo,… …   Español en México

Compartir el artículo y extractos

Link directo
Do a right-click on the link above
and select “Copy Link”