Teorema de Toda

Teorema de Toda

El teorema de Toda es un teorema demostrado por Seinosuke Toda en el artículo de 1991 "PP is as Hard as the Polynomial-Time Hierarchy", que le dio a su autor el Premio Gödel en 1998.

El teorema establece que toda la jerarquía polinomial PH está contenida en PPP, lo cual implica que PH está contenido en P#P.

#P es el problema de contar el número exacto de soluciones de una pregunta polinomialmente verificable (es decir, de una pregunta en NP), mientras que, a grandes rasgos, PP es el problema de dar una respuesta que es correcta al menos la mitad de las veces. La clase P#P, finalmente, corresponde a todos los problemas que pueden ser resueltos en tiempo polinomial si se tiene acceso a respuestas instantáneas a cualquier problema de conteo en #P.

Así, el teorema de Toda implica que para cualquier problema en jerarquía polinomial hay una reducción polinomial a un problema de conteo.[1]

Referencias


Wikimedia foundation. 2010.

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

Mira otros diccionarios:

  • Teorema fundamental del cálculo integral — Saltar a navegación, búsqueda El teorema fundamental del cálculo integral consiste (intuitivamente) en la afirmación de que la derivación e integración de una función son operaciones inversas. Esto significa que toda función continua integrable… …   Wikipedia Español

  • Teorema de Rouché-Capelli — Saltar a navegación, búsqueda Teorema de Rouché Capelli con algunas variantes también conocido como Teorema de Rouché Frobenius, se trata de un teorema de álgebra lineal que permite calcular el número de soluciones de un sistema lineal de… …   Wikipedia Español

  • Teorema de Sonnenschein-Mantel-Debreu — Teorema económico, formulado en primer lugar por Hugo F. Sonnenschein en 1972 y 1973 y complementado en 1974 por Rolf Mantel, así como por el propio Gérard Debreu. Evidencia que las funciones de demanda y oferta, resultantes del modelo de… …   Wikipedia Español

  • Teorema de la estadística del spin — Saltar a navegación, búsqueda El teorema de la estadística del spin de la mecánica cuántica establece la relación directa entre el spin de una especie de partícula con la estadística que obedece. Fue demostrado por Fierz y Pauli en 1940, y… …   Wikipedia Español

  • Teorema de Poincaré — Saltar a navegación, búsqueda Con el nombre de Teorema de Poincaré se conocen varios resultados, especialmente sobre Ecuaciones Diferenciales y Geometría Diferencial. Seguramente el más conocido de ellos es el que afirma que toda forma… …   Wikipedia Español

  • Teorema fundamental del álgebra — El teorema fundamental del álgebra establece que un polinomio en una variable, no constante y con coeficientes complejos, tiene tantas raíces[1] como indica su grado, contando las raíces con sus multiplicidades. En otras palabras, dado un… …   Wikipedia Español

  • Teorema de muestreo de Nyquist-Shannon — Función de interpolación g(t) para Fs=44100 muestras por segundo (estándar CD Audio). Excepto para t=0, el intervalo entre pasos por cero (líneas verticales verdes) representa el intervalo entre muestras ( 22,68 µs para este ejemplo). El teorema… …   Wikipedia Español

  • Teorema de los infinitos monos — De acuerdo con el segundo enunciado Borel Cantelli, con suficiente tiempo, un chimpancé escribiendo al azar podría escribir una obra de Shakespeare (o cualquier otro texto). El teorema de los infinitos monos afirma que un mono pulsando teclas al… …   Wikipedia Español

  • Teorema de la bola peluda — Si un campo vectorial sobre una esfera se simboliza por pelos de longitud constante, el teorema de la bola peluda estipula que la esfera contiene al menos un rizo. La figura contiene dos, uno en cada polo. En matemática, y más precisamente en… …   Wikipedia Español

  • Teorema de representación de Riesz — Hay varios teoremas bien conocidos en el análisis funcional mencionados como el teorema de representación de Riesz. El teorema de representación de espacios de Hilbert Este teorema establece una conexión importante entre un espacio de Hilbert y… …   Wikipedia Español

Compartir el artículo y extractos

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