Ejecicios Unidad 2

Fecha de entrega: 27 de noviembre.

1. Mostrar que NP  ⊆  PSPACE.

2. Sea coC la clase de los lenguajes cuyos complemento está en C.
   • Mostrar que P  ⊆  coNP.
   • Mostrar que P=NP implica NP=coNP.
3. 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.

4. (Sipser 7.21) DOUBLESAT = {⌊φ⌋ ∣ φ tiene al menos dos asignaciones satisfactoras } Mostrar que DOUBLESAT es NP completo (usando reducciones de Karp en tiempo polinomial).