Siguiente: Complejidad en redes de Un nivel arriba: Algunos problemas principales completos-NP Anterior: .

Tercera lista de programas

1. Teorema de Cook: Implemente la demostración del teorema de Cook. Dada una máquina de Turing y una descripción inicial construya la instancia de SAT que es equivalente a la convergencia de la máquina con la descripción dada. Ver: Hopcroft, Ullman: ``Int. to automata theory, languages and computation''. pp. 325-327.

2. Convierta instancias de SAT a instancias equivalentes de CNF-SAT. Convierta soluciones. Ver: Hopcroft, Ullman: ``Int. to automata theory, languages and computation''. pp. 328-330.

3. Convierta instancias de SAT a instancias equivalentes del problema de la programación entera. Convierta soluciones. Ver: Hopcroft, Ullman: ``Int. to automata theory, languages and computation''. pp. 338.

4. Convierta instancias de 3CNF a instancias equivalentes de ``Vertex_Cover''. Convierta soluciones. Ver: Hopcroft, Ullman: ``Int. to automata theory, languages and computation''. pp. 331-332.

5. Convierta instancias de 3CNF a instancias equivalentes de ``circuito hamiltoniano dirigido''. Convierta soluciones. Ver: Hopcroft, Ullman: ``Int. to automata theory, languages and computation''. pp. 333-335.

6. Convierta instancias de ``circuito hamiltoniano dirigido'' a instancias equivalentes de ``circuito hamiltoniano no-dirigido''. Convierta soluciones. Ver: Hopcroft, Ullman: ``Int. to automata theory, languages and computation''. pp. 335.

7. Convierta instancias de 3CNF a instancias equivalentes de 3DM. Convierta soluciones. Ver: Even: ``Graph algorithms'', Computer Science Press, Maryland. pp. 205-207.

8. Convierta instancias de 3DM a instancias equivalentes de 3XC. Convierta soluciones. Ver: Even: ``Graph algorithms'', Computer Science Press, Maryland. pp. 207.

9. Convierta instancias de 3CNF a instancias equivalentes de 3C. Convierta soluciones. Ver: Even: ``Graph algorithms'', Computer Science Press, Maryland. pp. 218-219.

10. Convierta instancias de 3C a instancias equivalentes de 3CP. Convierta soluciones. Ver: Even: ``Graph algorithms'', Computer Science Press, Maryland. pp. 221-223.

11. Convierta instancias de 3CNF a instancias equivalentes de CC. Convierta soluciones. Ver notas del curso.

12. Convierta instancias de 3CNF a instancias equivalentes de DSP. Convierta soluciones. Ver notas del curso.

13. Convierta instancias de 3CNF a instancias equivalentes del problema de asignamiento de recursos a tareas. Convierta soluciones. Ver notas del curso.
Siguiente: Complejidad en redes de Un nivel arriba: Algunos problemas principales completos-NP Anterior: .