Diferencia entre revisiones de «PSPACE-completo»
Contenido eliminado Contenido añadido
m Pequeñas correcciones WP:CEM. |
|||
Línea 23:
=== TQBF ===
Sea TQBF = { <F> : F es una formula booleana verdadera totalmente cuantificada }. De entrada F:
Si F no tiene cuantificador,
Si F=pF', evaluar recursivamente F'[p=1] y F'[p=0], aceptar si y solo si ambos la aceptan.
Si F=qF', evaluar recursivamente F'[q=1], F'[q=0] y aceptar si y solo si al menos una la acepta.
| |||