ESPACIOP-completo
De Wikipedia, la enciclopedia libre
En teoría de la complejidad computacional, la clase de complejidad ESPACIOP-completo (PSPACE-complete en inglés) es el subconjunto de los problemas de decisión en ESPACIOP y todo problema en ESPACIOP puede ser reducido a él en tiempo polinomial. Los problemas en ESPACIOP-completo pueden verse como los problemas más difíciles de la clase ESPACIOP. 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-completo es el problema de las tautologías booleanas que es muy parecido a 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:
Se puede ver que los problemas NP-completos se parecen a rompecabezas: ¿Existe alguna forma de colocar estos valores para encontrar la respuesta?
Los problemas en ESPACIOP-completo se parecen más a preguntas del estilo ¿Existe una movida que pueda hacerse para que cualquiera sea la próxima movida del oponente exista una movida ganadora para mí? Se trata de preguntas que alternan cuantificadores existenciales y universales. No resulta sorprendente que los rompecabezas correspondan a problemas NP-completos y los juegos correspondan a problemas en ESPACIOP-completo.
La definición de ESPACIOP-completo se basa en la noción de complejidad 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 no podría ser considerado un problema de ESPACIOP-completo mas sí 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 ESPACIOP-completo corresponden a los lenguajes sensitivos al contexto.
[editar] Enlaces externos
| clases de complejidad más importantes |
| L | NL | P | NP | Co-NP | NP-C | Co-NP-C | NP-hard | UP | #P | #P-C | NC | P-C |
| PSPACE | PSPACE-C | EXPTIME | EXPSPACE | BQP | BPP | RP | ZPP | PCP | IP | PH |
