PDF de programación - COMPUTABILIDAD Y COMPLEJIDAD

COMPUTABILIDAD Y COMPLEJIDAD

Guillermo Morales-Luna

Departamento de Computación

CINVESTAV-IPN

[email protected]

México, D. F. a 18 de enero de 2008

ii

Contenido

1 Conceptos básicos

1.1 Pruebas por contradicción . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Inducción matemática . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2
Inducción numérica
1.2.1
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Inducción recurrente . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2.2
1.3 Enumeración de Cantor
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.4 Lenguajes formales de programación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.4.1 Programas-while . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.4.2 Macros
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Semántica de los programas-while . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.4.3
1.5 Funciones computables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.6 Máquinas de Turing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.6.1
Introducción a las máquinas de Turing . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.6.2 Computaciones en máquinas de Turing . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.6.3 Modelos restringidos de máquinas de Turing . . . . . . . . . . . . . . . . . . . . . . . .
1.6.4 Computabilidad-Turing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.7 Tesis de Church . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.8 Propiedades de cerradura de funciones computables . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . .
1.9 Numerabilidad de la clase de funciones computables
1.9.1 Codificación de programas-while . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2 Funciones recursivas primitivas

2.1 Conceptos básicos
2.2 Funciones elementales

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2.1 Algunos otros esquemas de composición . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2.2 Clase de funciones elementales
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.3 Jerarquía de Grzegorczyk . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.3.1 Una escala de funciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

iii

1
2
3
4
5
6
8
10
10
12
13
14
14
16
16
18
19
20
22
24

29
29
34
34
36
39
39

iv

CONTENIDO

2.3.2 Propiedades de la escala . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.3.3 Niveles de la jerarquía . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.4 Función de Ackermann . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3 Funciones de apareamiento y universalidad

3.1 Funciones de apareamiento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.1.1 Algunas funciones de apareamiento . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.2 Reiteración de funciones de apareamiento . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.3 Función β de G¨odel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.3.1 Nociones de divisibilidad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.3.2 Teorema Chino del Residuo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.3.3 Función β de G¨odel

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.4 Universalidad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.4.1 Codificación de programas por números . . . . . . . . . . . . . . . . . . . . . . . . . .

3.4.2 Numerabilidad de la clase de máquinas de Turing . . . . . . . . . . . . . . . . . . . . .

3.4.3 La noción de “Universalidad” . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.4.4 Máquina Universal de Turing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.4.5 Universalidad en programas-while . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4 Teoría de la recursividad

4.1 Funciones recursivas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4.2 Problema de la parada . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4.3 Decidibilidad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4.3.1 Conjuntos decidibles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4.3.2 Proyecciones

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4.3.3 Problema de la parada (otra vez) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4.4 Teoremas de recursión . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4.5 Teoremas de autorreproducción . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4.6 Virus en programas-while . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4.6.1 Definiciones básicas

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4.6.2 Matrices infinitas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4.6.3 Teoremas de recursión . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4.6.4 Construcción de virus

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4.6.5 Malas noticias: No hay detección universal de virus

. . . . . . . . . . . . . . . . . . .

5 Irresolubilidad

5.1 Teorema de Rice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

40

43

44

49

49

51

53

57

57

61

63

65

65

66

67

68

71

73

73

74

74

74

75

76

77

78

78

79

79

80

81

81

83

83

CONTENIDO

v

5.3

5.4

86
5.2 Problema de la correspondencia de Post . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
86
5.2.1 Presentación del Problema de Post . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
89
5.2.2 Una aplicación de PCP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
91
Irresolubilidad de problemas en GLC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
91
5.3.1 Reducción de problemas al problema de la parada . . . . . . . . . . . . . . . . . . . .
93
5.3.2 Algunos otros problemas irresolubles . . . . . . . . . . . . . . . . . . . . . . . . . . . .
94
Irresolubilidad en la Aritmética . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.4.1 Aritmética de Peano . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
94
5.4.2 El teorema de Goodstein . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
5.4.3 La conjetura de Catalan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
5.5 Clasificación de problemas irresolubles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
5.5.1 Computaciones con oráculos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
. . . . . . . . . . . . . . . . . . . . . . . 108
5.5.2 Enumerabilidad recursiva relativa a oráculos

6 Teoremas de jerarquía

6.2 Clases de problemas

111
6.1 Ordenes de funciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
6.1.1 Definiciones básicas
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
6.1.2 Algunas clases de funciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
6.1.3 Límites inferiores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
6.2.1 Problemas de decisión . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
6.2.2 Problemas de solución . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
6.2.3 Comprobadores y resolvedores
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
6.3 Complejidades de tiempo y espacio . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
6.3.1 Dispositivos de cómputo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
6.3.2 Tiempos y espacios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
6.4 Jerarquía en espacio . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
6.5 Jerarquía en tiempo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
6.6 Algunas relaciones entre clases
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118
6.7 Jerarquías en clases no-deterministas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
6.8 Teorema de Borodin y consecuencias . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120

7 Completitud-NP

7.1 Clases de problemas

121
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
7.1.1 Reducibilidades . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
7.2 Problemas difíciles y completos en clases polinomiales
. . . . . . . . . . . . . . . . . . . . . . 123
7.3 Formas proposicionales y el teorema de Cook . . . . . . . . . . . . . . . . . . . . . . . . . . . 124

vi

CONTENIDO

7.3.1 Formas booleanas

. . . . . . . . . . . . . . . . . . . . . . . . . . . .