Ejecicios Unidad 2
Fecha de entrega: 27 de noviembre.
-
Mostrar que NP $\subseteq$ PSPACE.
-
Sea coC la clase de los lenguajes cuyos complemento está en C. * Mostrar que P $\subseteq$ coNP. * Mostrar que P=NP implica NP=coNP.
- El problema de la autopista con peaje (turnpike problem) es el siguiente:
“dadas n(n − 1) / 2 distancias entre pares de puntos,
¿les corresponde alguna configuración de n puntos en una línea?”.
- Definir un lenguaje que corresponde a ese problema.
- Mostrar que ese lenguaje está en NP.
- (Sipser 7.21) $DOUBLESAT= { \lfloor \varphi \rfloor \mid \varphi$ tiene al menos dos asignaciones satisfactoras $}$ Mostrar que DOUBLESAT es NP completo (usando reducciones de Karp en tiempo polinomial).