Numeral-P-completo

Numeral-P-completo

En teoría de la complejidad computacional, la clase de complejidad #P-completo (se pronuncia numeral-P-completo) es el conjunto de los problemas de conteo que pertenecen a #P tales que todo problema de #P se puede reducir en todos los de $P-completo en tiempo polinómico.

Algunos ejemplos de #P-completo incluyen:

  • ¿Cuantas asignaciones de variables satisfacen una fórmula dada?
  • ¿Cuantas correspondencias perfectas hay en un grafo bipartito?

Se piensa que no hay algoritmos en tiempo polinómico para resolver problemas #P-completos. Inclusive, no se conocen algoritmos deterministas que puedan dar una solución aproximada de calidad razonable.

Sin embargo, existen algoritmos probabilísticos que dan una buena aproximación a algunos problemas #P-completos con una muy buena probabilidad. Esta es una de las mejores demostraciones del potencial de los algoritmos probabilísticos.

Resulta sorprendente que algunos problemas #P-completos corresponden a problemas en P. El segundo de los ejemplos dados anteriormente está en esta categoría. La pregunta "¿Existe una correspondencia perfecta para un grafo bipartito?" puede ser respondida en tiempo polinómico. Específicamente, para un grafo con V vértices y E aristas, la pregunta se puede responder en tiempo O(VE).


Wikimedia foundation. 2010.

Игры ⚽ Поможем решить контрольную работу

Mira otros diccionarios:

  • Numeral-P-completo — En teoría de la complejidad computacional, la clase de complejidad #P completo (se pronuncia numeral P completo) es el conjunto de los problemas de conteo que pertenecen a #P tales que todo problema de #P se puede reducir en todos los de $P… …   Enciclopedia Universal

  • Numeral-P — En teoría de la complejidad computacional, la clase de complejidad #P (pronunciado numeral P) es el conjunto de los problemas de conteo asociados a los problemas de decisión en el conjunto NP. Un problema en NP se describe usualmente con la… …   Wikipedia Español

  • Leslie Valiant — Leslie Gabriel Valiant (nacido el 28 de marzo de 1949) es un informático teórico británico. Educado en el King s College, Cambridge, Imperial College London y la Universidad de Warwick donde recibió su Ph.D. en ciencias de computación en 1974.… …   Wikipedia Español

  • Teoremas de incompletitud de Gödel — Kurt Gödel a los 19 años de edad, cinco años antes de la demostración de los teoremas. Los teoremas de incompletitud de Gödel son dos célebres teoremas de lógica matemática demostrados por Kurt Gödel en 1930. Ambos están relacionados con la… …   Wikipedia Español

  • Nombre — (Del lat. numen.) ► sustantivo masculino 1 Palabra que designa los objetos físicos, síquicos o ideales: ■ la esperanza es el nombre de una virtud teologal. 2 Término o conjunto de ellos con que se designa a una persona: ■ su nombre es Juan;… …   Enciclopedia Universal

  • Septuaginta — Columna en caracteres unciales de los textos de Esdras, tal como se les lee en la Biblia Septuaginta. La Biblia griega, comúnmente llamada Biblia Septuaginta o Biblia de los Setenta, y generalmente abreviada simplemente LXX, fue traducida de… …   Wikipedia Español

  • Francisco Domínguez Brito — Saltar a navegación, búsqueda Francisco Domínguez Brito …   Wikipedia Español

  • medio — (Del lat. medius.) ► adjetivo 1 Que es igual a la mitad de un todo o de un entero: ■ se bebió media botella de vino; ya he leído medio libro; con media docena de huevos es suficiente. 2 Que está aproximadamente entre dos extremos: ■ pertenece a… …   Enciclopedia Universal

  • Nomenclatura de hidrocarburos acíclicos — La Nomenclatura de Hidrocarburos Acíclicos es una metodología establecida para denominar y agrupar los hidrocarburos cuyas cadenas principales o secundarias son todas abiertas. Cuando todos los carbonos del compuesto tienen cuatro enlaces simples …   Wikipedia Español

  • Tarot (juego de cartas) — Para otros usos de este término, véase Tarot. El tarot es un juego de cartas que utiliza la baraja de tarot y se practica generalmente con cuatro jugadores aunque existen variantes desde dos hasta ocho jugadores. Este artículo comienza con la… …   Wikipedia Español

Compartir el artículo y extractos

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