Revisión del 14:07 9 sep 2004 editar Ascánder (discusión · contribs.) Autoverificados 30 918 ediciones Traducción de en:		Revisión del 14:24 23 nov 2004 editar deshacer Ascánder (discusión · contribs.) Autoverificados 30 918 ediciones m determinístico --> determinista Ir a siguiente diferencia →
Línea 1: En [[complejidad computacional\|teoría de la complejidad computacional]], la [[clase de complejidad]] '''PSPACE-completo''' es el subconjunto de los [[problema de decisión\|problemas de decisión]] en [[PSPACE]] y todo problema es PSPACE puede ser reducido a él en tiempo polinomial. Los problemas en PSPACE-completo pueden verse como los problemas más difíciles de la clase 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 PSPACE-completo es el ~~problama~~problema de las tautologías ~~booleanes~~booleanos 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. Una instancia de este problema sería: : <math>\exists x_1 \, \forall x_2 \, \exists x_3 \, \forall x_4: (x_1 \or \neg x_3 \or x_4) \and (\neg x_2 \or x_3 \or \neg x_4)</math> Línea 11: --> La definición de PSPACE-completo se basa en la noción de [[complejidad ~~asimtótica~~asintótica]], que es el tiempo en, función del tamaño ''n'' que toma un problema para ser resuelto cuando ''n'' crece de forma ilimitada. El [[Ajedrez]], sobre un tablero de 8 × 8 ~~board~~ no podría ser considerado un problema de PSPACE-completo mas sisí su generalización a tableros de tamaño arbitrario. Por ello, para estudiar la complejidad de los juegos, se estudian sus versiones generalizadas. Los problemas de PSPACE-completo corresponden a los [[lenguajes sensitivos al contexto]].

Diferencia entre revisiones de «PSPACE-completo»