Revisión del 20:17 1 jun 2009 editar CabreraDominguezYGarcia (discusión · contribs.) 8 ediciones mSin resumen de edición ← Ir a diferencia anterior		Revisión del 20:29 1 jun 2009 editar deshacer CabreraDominguezYGarcia (discusión · contribs.) 8 ediciones m Arreglando un par de resquicios de cuando el artículo se llamaba ESPACIOP-completo Ir a siguiente diferencia →
Línea 1: En [[Complejidad computacional\|teoría de la complejidad computacional]], la [[clase de complejidad]] '''~~ESPACIOP~~PSPACE-completo''' (PSPACE-complete en [[idioma inglés\|inglés]]) es el subconjunto de los [[problema de decisión\|problemas de decisión]] en [[PSPACE\|ESPACIOP]] y todo problema en ~~ESPACIOP~~PSPACE puede ser reducido a él en tiempo polinomial. Los problemas en ~~ESPACIOP~~PSPACE-completo pueden verse como los problemas más difíciles de la clase ~~ESPACIOP~~PSPACE. Se sospecha fuertemente que estos problemas están fuera de las clases de complejidad P y NP, pero no hay prueba de ello. Se sabe que no están contenidos en la clase [[NC]]. El problema más básico de ~~ESPACIOP~~PSPACE-completo es el problema de las tautologías booleanas que es muy parecido a [[Problema de satisfacibilidad booleana\|SAT]] salvo que se quiera saber si todas las asignaciones de variables de una expresión booleana hacen que la expresión sea cierta. En [[Complejidad computacional\|teoría de complejidad]], un [[problema de decisión]] es PSPACE-completo cuando pertenece a la [[ESPACIOP\|clase de complejidad PSPACE]] y cada problema en PSPACE puede ser reducido a él en tiempo polinómico (véase [[Complejidad computacional\|completo (complejidad)]]). Puede pensarse que los problemas que son PSPACE-completos son los más difíciles de resolver en la clase PSPACE. Se sospecha ampliamente que estos problemas pueden estar fuera de las conocidas clases de complejidad P y NP, pero no es un hecho que haya sido demostrado. Sin embargo se tiene la certeza de que están fuera de NC.

Diferencia entre revisiones de «PSPACE-completo»