Modelos Abstractos 13d19

Modelos Abstractos de Cálculo Elvira Mayordomo Cámara 18 de enero de 2008

Cap´ıtulo 0

Presentaci´ on La asignatura de Modelos Abstractos de Cálculo consta de dos partes: computabilidad (también llamada recursividad) y complejidad, cada una de ellas ocupa aproximadamente un 50 % de las clases de teor´ıa y problemas. Parte I: Computabilidad. Los contenidos fundamentales son los siguientes: Existen problemas que no se pueden resolver con ning´ un algoritmo. Veremos ejemplos importantes de estos problemas “irresolubles” y métodos para saber que un problema es de este tipo. Se conjetura que cualquier noción razonable de algoritmo da lugar al mismo conjunto de problemas resolubles. EJERCICIOS Escribir los siguientes procedimientos ada (y probarlos): 0.1. Function check(f:file type; n:integer) return boolean; {Pre: f es un fichero que contiene un programa ada que lee de teclado un u ńico valor entero. Post: devuelve true si el programa contenido en f con entrada n termina; devuelve false si se queda “colgado”} 0.2. Procedure fermat(n:in integer; x,y,z:out integer); 1

´ CAPÍTULO 0. PRESENTACION

2

{Pre: n ∈ IN Post: x, y, z ∈ IN tales que xn + y n = z n } Parte II: Complejidad. En esta parte veremos: Cómo medir la velocidad de un algoritmo en función del tama˜ no de la entrada. Existen problemas que se pueden resolver en tiempo razonable y otros no, se trata de los problemas tratables e intratables. Nos dedicaremos a los segundos. EJERCICIO Escribir un programa en ada que resuelva el siguiente problema (atención a la eficiencia): 0.3. Se trata de un viajante que necesita recorrer n ciudades en el menor tiempo posible. Disponemos de la distancia correspondiente a cada pareja de ciudades, d(i, j) es la distancia de la ciudad i a la j, las ciudades están numeradas correlativamente de 1 a n. Escribir un programa que dados n y d(i, j) para todo i, j encuentre un camino (una ordenación de las n ciudades) de forma que la suma de las distancias recorridas en ese camino sea la m´ınima posible.

Bibliograf´ıa [Jones] N. Jones: “Computability and Complexity From a Programming Perspective”, MIT press, 1997. [Cu80] N.J. Cutland: “Computability: An Introduction to Recursive Function Theory”, Cambridge University Press, 1980. [So87] R. Soare: “Recursively Enumerable Sets and Degrees”, SpringerVerlag, 1987. [LP81] H.R. Lewis, C.H. Papadimitriou: “Elements of the Theory of Computation”, Prentice-Hall, 1981. [GJ78] M. Garey, D. Johnson: “Computers and Intractability: A Guide to the Theory of NP-Completeness”, Freeman, 1978. [HMU02] J.E. Hopcroft, R. Motwani, J.D. Ullman, “Introducción a la Teor´ıa de Autómatas, Lenguajes y Computación”, AddisonWesley, 2002. ` [SACL01] M. Serna, C. Alvarez, R. Cases, A. Lozano: “Els l´ımits de la computació. Indecidibilitat i NP-completesa”, Edicions UPC, 2001.

3

Cap´ıtulo 1

Preliminares. Numerabilidad y diagonalizaci´ on Referencia: Cap´ıtulo 1 de [LP81]. En el estudio de la calculabilidad y la complejidad, es imprescindible formular afirmaciones rigurosas y relacionarlas mediante deducciones rigurosas. En este contexto el lenguaje matemático nos permitirá expresarnos con precisión y agilidad. Este cap´ıtulo contiene un repaso de la notación y conceptos principales de lógica, demostraciones, teor´ıa de conjuntos, lenguajes y alfabetos, y funciones, además de una breve introducción a la teor´ıa de cardinales y a la diagonalización.

1.1.

Preliminares

1.1.1.

Notaci´ on l´ ogica: proposiciones

Una proposición o enunciado es una frase declarativa ó sentencia que podemos clasificar como cierta o falsa, por ejemplo “α es la primera letra del alfabeto griego”, o “el sol se pone por el este”. Si P y Q son dos proposiciones, podemos formar otras mediante las conectivas lógicas ¬, ∧, ∨, ⇒, ⇔:

4

CAPÍTULO 1. PRELIMINARES. NUMERABILIDAD Y ...

Notación formal ¬P P ∨Q P ∧Q P ⇒Q P ⇔Q

5

Significado informal “no P ” “P ó Q” “P y Q” “P implica Q” ó “si P entonces Q” ó “P sólo si Q” “P si y sólo si Q” ó “P es equivalente a Q”

La asignación de valores de verdad a las proposiciones compuestas mediante las conectivas ∧, ∨, ¬ corresponde a la interpretación usual de las palabras y, o y no, respectivamente. El valor de verdad de la proposición P ⇒ Q equivale al de (¬P ) ∨ Q de manera que la asignación de valores de verdad P = cierto y Q = f also es la u ńica que hace falsa P ⇒ Q. La proposición P ⇒ Q es equivalente a (¬Q) ⇒ (¬P ). P ⇒ Q NO es equivalente a Q ⇒ P . No es equivalente decir “Si Juan es inglés entonces Juan es europeo” a decir “Si Juan es europeo entonces Juan es inglés”. El valor de verdad de P ⇔ Q corresponde al de (P ⇒ Q) ∧ (Q ⇒ P ). Para ahorrarnos paréntesis estableceremos precedencias entre las diferentes conectivas. En orden de precedencia decreciente tenemos: ¬, ∧, ∨, ⇒, ⇔ 1.1.2.

Notaci´ on l´ ogica: predicados

Un predicado es una sentencia que contiene una ó más variables. Cada variable puede tomar valor en un cierto universo. Por ejemplo, si x es un entero (variable en el universo de los enteros), el predicado P (x) = (x es primo ∧ (x ≤ 100)) cumple que P (19) = cierto y P (20) = f also. Cuando todas las variables se sustituyen por valores, el predicado se convierte en una proposición. Por ejemplo, P (33) = (33 es primo ∧ (33 ≤ 100)) es una proposición falsa. Un predicado como el anterior, que contiene sólo una variable, se llama propiedad. Si P (x) es cierto, decimos que x


6

tiene o cumple la propiedad P ; si es falso, decimos que x no tiene o no cumple la propiedad P . Otra forma de obtener proposiciones a partir de predicados consiste en cuantificar las variables. Si tenemos un predicado P (x), podemos construir dos proposiciones nuevas mediante el cuantificador existencial ∃ y el cuantificador universal ∀ de la siguiente forma: Notación formal ∃xP (x) ∀xP (x)

Significado informal Para alg´ un x, P (x) Para todo x, P (x)

La proposición ∃xP (x) es cierta si P (x) es cierto para alg´ un valor de x, mientras que ∀xP (x) es cierta si P (x) es cierto para todo posible valor de x. En el caso del cuantificador existencial, se introduce también el s´ımbolo 6 ∃, que permite abreviar el enunciado ¬(∃P (x)) con 6 ∃P (x). El s´ımbolo ∃ se puede considerar como la extensión de ∨ al caso infinito (y ∀ como extensión de ∧). El universo de valores que puede tomar una variable (los n´ umeros naturales, las palabras sobre un determinado alfabeto, etc) depende del predicado concreto y es usual no especificarlo si se puede deducir fácilmente del contexto (por ejemplo, en el caso del predicado P (x) del ejemplo anterior). Por otro lado, podemos escribir ∃x, y, z ∈ IN+ x2 + y 2 = z 2 para establecer claramente que x, y, z toman valores naturales positivos. También podemos escribir ∀n > 2 P (n) para indicar que n toma valores naturales mayores que 2. Existen toda una serie de equivalencias entre sentencias, por ejemplo las llamadas leyes de Morgan: 1. ¬(P ∧ Q) ⇔ (¬P ) ∨ (¬Q) 2. ¬(∀xP (x)) ⇔ ∃x ¬P (x) y las simétricas que se obtienen intercambiando las conectivas ∧ y ∨, en 1, y los cuantificadores ∀ y ∃, en 2.


1.1.3.

7

Demostraciones

Un teorema es cualquier proposición para la que existe una demostración. A lo largo de esta asignatura utilizaremos algunos métodos de demostración: 1. Demostración directa: a partir de una serie de teoremas ya conocidos deducimos un nuevo teorema. 2. Reducción al absurdo: para demostrar P demostramos que su negación implica una contradicción, es decir ¬P ⇒ f also. Por ejemplo, para demostrar X ⇒ Y demostramos que X ∧ ¬Y implica que todos los naturales son pares. Como hemos visto anteriormente, es equivalente demostrar P ⇒ Q que demostrar ¬Q ⇒ ¬P , y para demostrar P ⇔ Q hemos de demostrar que P ⇒ Q y Q ⇒ P . 1.1.4.

Notaci´ on de conjuntos

Dado un universo de elementos (por ejemplo, los n´ umeros naturales), representaremos con {x | P (x)} el conjunto de los elementos que cumplen la propiedad P . Utilizaremos las operaciones: 1. Unión: A ∪ B = {x | x ∈ A ∨ x ∈ B}. 2. Intersección: A ∩ B = {x | x ∈ A ∧ x ∈ B}. 3. Diferencia: A − B = {x | x ∈ A ∧ x 6∈ B}. 4. Complementación: A = {x | x 6∈ A}. 5. Producto cartesiano: A×B = {(x, y) | x ∈ A ∧ y ∈ B} (el conjunto de todos los pares ordenados de elementos de A y de B). Obsérvese que la equivalencia entre las expresiones de conjuntos y los predicados correspondientes permite deducir las igualdades A = A, A − B = A ∩ B, A ∩ B = A ∪ B.


8

Dados dos conjuntos A y B diremos que A está inclu´ıdo en B (o A es un subconjunto de B), representado con A ⊆ B, si todo elemento de A pertenece a B, es decir, si es cierta la proposición ∀x x ∈ A ⇒ x ∈ B Para demostrar una igualdad de conjuntos A = B demostraremos A ⊆ B y B ⊆ A. Representaremos con A 6⊆ B el hecho de que A no está inclu´ıdo en B (¬(A ⊆ B)). Cuando se cumple que A ⊆ B pero B 6⊆ A, diremos que A está estrictamente inclu´ıdo en B, y lo representaremos con A ⊂ 6= B. Representaremos por kAk el cardinal de un conjunto A (en el caso de conjuntos finitos, el n´ umero de elementos que lo componen). Dado un conjunto A cualquiera, el conjunto de todos los subconjuntos de A se llama conjunto de las partes de A y se denota P(A). Si kAk = n entonces kP(A)k = 2n . 1.1.5.

Lenguajes

Hacemos un repaso rápido de los primeros conceptos sobre lenguajes. Un alfabeto es un conjunto finito no vac´ıo. Sus elementos se llaman s´ımbolos. Una palabra sobre un alfabeto es una secuencia finita de s´ımbolos. La secuencia que no contiene ning´ un s´ımbolo se llama palabra vac´ıa y se representa con λ. Un lenguaje sobre un alfabeto es un conjunto de palabras. Dado un alfabeto Σ, Σ∗ es el lenguaje de todas las palabras sobre Σ. La longitud de una palabra x es el n´ umero de s´ımbolos que tiene, denotado como |x|. Dado un alfabeto Σ y n ∈ IN, Σn es el conjunto de las palabras de longitud n, y Σ≤n el conjunto de las palabras de longitud menor o igual a n.


9

Por ejemplo, si Σ = {0, 1}, Σ0 = {λ}, Σ2 = {00, 01, 10, 11}. La siguiente proposición nos da el n´ umero de palabras de cada longitud y se puede demostrar fácilmente por inducción. Proposición 1.1 Dado un alfabeto Σ y un n ∈ IN, kΣn k

= kΣkn

kΣ≤n k =

kΣkn+1 −1 kΣk−1

En esta asignatura trataremos a menudo con conjuntos de lenguajes, que llamaremos clases. 1.1.6.

Funciones

Nota muy importante: En esta asignatura utilizaremos la palabra función EXCLUSIVAMENTE con el significado matemático que se explica a continuación. Para evitar confusiones nunca la utilizaremos para denotar procedimientos o programas con un sólo parámetro de salida, que en muchos lenguajes de programación reciben también este nombre. Dados dos conjuntos A y B, una función f : A → B es, informalmente, una forma de asociar a x ∈ A un elemento de B que llamamos f (x). Nos referiremos siempre a funciones parciales. Es decir, una función f : A → B no tiene que estar definida para todos los elementos de A. Ejemplo 1.2 Sea f : IN → IN la función definida como: f (2n) = n, o equivalentemente, (

f (x) =

x/2 si x es par indefinido en otro caso

Definición 1.3 El dominio de una función f : A → B es el conjunto Dom(f ) definido como sigue Dom(f ) = {x | f (x) está definida } Definición 1.4 El rango de una función f , también llamado imagen de f , es el conjunto Im(f ) (también Rang(f )) Im(f ) = {f (x) | x ∈ Dom(f )}


10

As´ı pues, Im(f ) es el conjunto de las imágenes de la función f . Si f : A → B entonces Dom(f ) ⊆ A, Im(f ) ⊆ B. Como convenio de notación, dadas dos funciones f y g, sólo escribiremos f (x) = g(y) cuando x ∈ Dom(f ) e y ∈ Dom(g), es decir, si f (x) y g(y) están ambas indefinidas diremos que f (x) 6= g(y). Existe una función de dominio vac´ıo, que llamaremos la función vac´ıa, y que está indefinida en todos los puntos. Ejemplo 1.5 La función f : IN → IN que devuelve la raiz cuadrada exacta de un n´ umero la podemos definir como: ( √ x si x es un cuadrado perfecto f (x) = indefinido en otro caso En este caso Dom(f ) = {x | x es un cuadrado perfecto} y Im(f ) = IN. Definición 1.6 f es una función inyectiva si se cumple que para cada x, y ∈ Dom(f ) con x 6= y, f (x) 6= f (y). Es importante notar que la definición de inyectividad se refiere sólo a los puntos donde está definida la función. Por ejemplo la función vac´ıa es trivialmente inyectiva. Definición 1.7 Si f es una función inyectiva f : A → B , definimos la inversa de f , f −1 : A → B, de la siguiente forma: para cada z ∈ Im(f ) f −1 (z) = x tal que f (x) = z. Notar que Dom(f −1 ) = Im(f ). Definición 1.8 f : A → B es suprayectiva si Im(f ) = B. Definición 1.9 f : A → B es total si Dom(f ) = A. Definición 1.10 f : A → B es una biyección si f es total, inyectiva y suprayectiva. Definición 1.11 Dadas dos funciones f, g : A → B, se dice que f extiende a g si 1. Dom(g) ⊆ Dom(f ),


11

2. ∀x ∈ Dom(g), f (x) = g(x). Definición 1.12 Dada f : A → B y C ⊆ A, la restricción de f a C, f /C, es la función f /C : C → B de dominio Dom(f /C) = C ∩ Dom(f ) y definida como f /C(x) = f (x) para x ∈ C ∩ Dom(f ). Ejemplo 1.13 Sea f la función definida en el ejemplo 1.5. La función ( √ x si x es un cuadrado perfecto g(x) = 0 en otro caso es una extensión total de f . Definición 1.14 Dadas f : A → B y g : B → C tales que Im(f ) ⊆ Dom(g), la composición de f y g, g ◦ f , es la función g◦f :A→C definida como g ◦ f (x) = g(f (x)) para x ∈ Dom(f ). Definición 1.15 Dado un conjunto A, su función caracter´ıstica es: (

χA (x) =

1.2.

1 si x ∈ A 0 si x 6∈ A

Numerabilidad

Una definición intuitiva de cardinal de un conjunto es el n´ umero de elementos que tiene. Si suponemos que n´ umero quiere decir n´ umero natural, entonces no podemos hablar de cardinal de conjuntos como IN. Si itimos infinito como posible n´ umero de elementos, entonces tanto IN como IR tienen infinitos elementos. Sin embargo, nos gustar´ıa poder expresar que hay más reales que naturales. En la b´ usqueda de una definición de cardinal, comparamos el conjunto de los pares y el de los impares:


12

pares 0, 2, 4, 6, . . . , 2n, . . . impares 1, 3, 5, 7, . . . , 2n − 1, . . . Parece que hay el mismo n´ umero de pares que de impares, porque tenemos una biyección entre los dos conjuntos. Esta es exactamente la definición de cardinal. Definición 1.16 Dos conjuntos A y B tienen el mismo cardinal si existe una biyección f : A → B . Nota: Es equivalente decir que existe una inyección total de A en B y otra de B en A. Nota: Si A tiene el mismo cardinal que B y B tiene el mismo cardinal que C, entonces A tiene el mismo cardinal que C. En el caso finito esta definición se corresponde con lo que dec´ıamos al principio de este sección: dos conjuntos de tres elementos {A, B, C}, {X, Y, Z} tienen el mismo cardinal, mientras que {A, B, C, D}, {X, Y, Z} no lo tienen. En el caso infinito esto se corresponde con la idea de que hay tantos pares como naturales 0 1 2 3 4 ... 0 2 4 6 8 ...

f (n) = 2n

hay tantos naturales como potencias de dos 0 1 2 3 4 ... 1 2 4 8 16 . . .

f (n) = 2n

Por supuesto, con cardinales infinitos no se puede operar como con finitos: ¿Cuánto vale ∞ − ∞? Depende IN− pares = impares (cardinal infinito) IN−IN= ∅ (cardinal 0) IN−{1, 2, 3, 4, . . .} = {0} (cardinal 1) Esto nos lleva a la observación de que los naturales tienen muchos subconjuntos con el mismo cardinal que IN. Esto sólo puede pasar para conjuntos infinitos, y de hecho podr´ıamos definir “A es un conjunto infinito si existe B ⊆ A con B 6= A y B tiene el mismo cardinal que A”. A partir de ahora trataremos los infinitos más peque˜ nos, llamados numerables.


13

Definición 1.17 A es numerable si A es finito ó A tiene el mismo cardinal que IN. Es decir, si A es numerable infinito tenemos una biyección f : IN → A, lo que nos permite enumerar los elementos de A y podernos referir a f (0) como “ceroésimo elemento de A”, a f (1) como “primer elemento de A”, . . ., f (x) como “x-ésimo elemento de A”. Otra forma intuitiva de verlo es: si A es numerable infinito tenemos una biyección g : A → IN, lo que nos permite dar a cada elemento x ∈ A su n´ umero de orden dentro de A, x es el elemento g(x)-ésimo de A. Veamos algunas propiedades básicas de los numerables (algunas de las demostraciones se dejan como ejercicios): Propiedad 1.18

IN es numerable.

Si A ⊆ B y B es numerable, entonces A es numerable. Propiedad 1.19 Si existe una inyecci´ on total f : A → IN, entonces A es numerable. Si existe una funci´ on suprayectiva f : IN → A, entonces A es numerable. Dem. Para la primera parte, si definimos g : A → Im(f ) como g(x) = f (x) ∀x ∈ Dom(f ), entonces g es total e inyectiva, por serlo f , y además suprayectiva, por estar definida de A en Im(f ), luego g es una biyección. Por tanto A tiene el mismo cardinal que Im(f ). Como Im(f ) ⊆ IN y IN es numerable, por la propiedad anterior Im(f ) es numerable y por tanto también lo es A. La segunda parte se demuestra de manera análoga. Ejemplos 1.20 de conjuntos numerables. IN × IN Definimos f : IN × IN → IN que corresponde al siguiente recorrido de los puntos de IN × IN


14

es decir, recorrido primero por diagonales: primero los puntos que suman 0, luego los que suman 1, etc. f (n, m) =

(1 + n + m)(n + m) +m 2

Otros recorridos posibles:

IN × IN × IN Sea f biyección de IN × IN en IN. Entonces g : IN × IN × IN → IN definida como g(x, y, z) = f (f (x, y), z) es biyección: • inyectiva. Si (x, y, z) 6= (x0 , y 0 , z 0 ): si (x, y) 6= (x0 , y 0 ) entonces f (x, y) 6= f (x0 , y 0 ) y por tanto f (f (x, y), z) 6= f (f (x0 , y 0 ), z 0 ) si (x, y) = (x0 , y 0 ) entonces z 6= z 0 (ya que (x, y, z) 6= (x0 , y 0 , z 0 )). Por tanto f (f (x, y), z) 6= f (f (x, y), z 0 ).


15

• total: por serlo f . • suprayectiva: Im(g) = Im(f /Im(f )×IN ) = Im(f /IN×IN ) = Im(f ). Im(f ) = IN (por ser f suprayectiva). Z

(

f (x) =

2x si x ≥ 0 −2x − 1 si x < 0

f es biyección de Z en IN. (Basta ver que los positivos van a los pares y los negativos a los impares). En general, tenemos la siguiente propiedad para productos cartesianos: Propiedad 1.21 Si A y B son numerables, entonces A×B es numerable. Q Como Z y IN son numerables, también lo es Z × IN (propiedad 1.21). Sea f la función total: f : Q → Z × IN q 7→ (n, m) con

n m

fracción irreducible de q

f es inyectiva, ya que una fracción irreducible representa un u ńico n´ umero racional. Por la propiedad 1.19, Q es numerable. Dado Σ un alfabeto, Σ∗ es el conjunto de todas las palabras sobre Σ. No podemos enumerar Σ∗ por orden alfabético (ej: Σ = {0, 1}, λ, 0, 00, 000, . . .) ya que hay infinitas palabras empezando por la primera letra del alfabeto, y nunca llegar´ıamos a las que empiezan por la segunda. La forma de hacer una biyección de IN en Σ∗ es enumerar las palabras por orden lexicográfico por longitudes, es decir, por longitudes, y dentro de cada longitud por orden alfabético. f : Σ∗ → IN |w| −1 w 7→ kΣk − 1+ “lugar de w por orden kΣk−1 alfabético en longitud |w|”


16

Nota: “Lexicográfico por longitudes” lo abreviaremos como lexicográfico. En cap´ıtulos sucesivos fijaremos un lenguaje de programación de alto nivel. Cada programa podemos codificarlo como una cadena de caracteres, es decir, una palabra sobre un alfabeto finito Σ (el alfabeto de los caracteres isibles). Por tanto podemos establecer una biyección del conjunto de todos los programas en un subconjunto de Σ∗ . Por esta razón hay una cantidad numerable de programas.

1.3.

Diagonalizaci´ on

En esta sección vamos a demostrar que algunos conjuntos son no numerables usando una técnica de Cantor llamada diagonalización. Esta técnica consiste en, dado un conjunto numerable A, construir un elemento x 6∈ A por etapas. Lema 1.22 Sea A un conjunto numerable, A ⊆ [0, 1] (donde [0, 1] es el intervalo de los n´ umeros reales entre 0 y 1). Entonces existe x ∈ [0, 1] tal que x 6∈ A. Dem. Por definición de numerable, existe una biyección f : IN → A. Dado n ∈ IN, denoto f (n) como rn . Entonces Im(f ) = A = {r0 , r1 , r2 , r3 , . . . , rn , . . .} Consideremos a los n´ umeros de A escritos en binario. Dados i, j ∈ IN denotamos como ri [j] al (j +1)-ésimo bit de la representación en binario de ri , es decir, si ri = 0, 00101

ri [2] = 1 ri [0] = 0

Vamos a construir x ∈ [0, 1] tal que ∀i ∈ IN, x 6= ri como sigue (

x[i] =

1 si ri [i] = 0 0 si ri [i] = 1

de esta forma ∀i x[i] 6= ri [i], y por tanto ∀i x 6= ri .


17

(Esto es lo que se llama diagonalización, construir x que cumpla x 6= r0 x 6= r1 ... x 6= rn ...

usando x[0] usando x[1] ... usando x[n] ...

es decir, cumplir una lista de objetivos x 6= r0 , x 6= r1 , . . ., x 6= rn , . . . de forma constructiva). Por construcción x 6∈ {r0 , r1 , . . .} = A. Pero x es la representación en binario de un n´ umero entre 0 y 1, luego x ∈ [0, 1]. Nota bene. Hay n´ umeros (los decimales periódicos) que tienen doble representación en binario. 0, 0ˆ1 = 0, 1 0, 010ˆ1 = 0, 11 etc. Pero podemos considerar el conjunto de todas las representaciones binarias de los elementos de A en lugar de A en la demostración anterior. (Si A es numerable, también lo es el conjunto de todas sus representaciones en binario, que son como máximo dos por cada n´ umero). Teorema 1.23 [0, 1] no es numerable. Dem. Reducción al absurdo. Supongamos que [0, 1] es numerable, entonces por el lema anterior existe x ∈ [0, 1] tal que x ∈ 6 [0, 1]. Esto es una contradicción, luego [0, 1] no es numerable. Teorema 1.24 IR no es numerable. Dem. Como [0, 1] ⊆ IR no es numerable, por la propiedad 1.18, IR no es numerable. Teorema 1.25 El conjunto de las funciones totales de IN en IN no es numerable. Dem. Vamos a diagonalizar en S, el conjunto de todas las funciones totales de IN en IN.


18

Lema 1.26 Sea A un conjunto numerable, A ⊆ S. Entonces existe x ∈ S tal que x 6∈ A. Dem. Por definición de numerable, existe una biyección F : IN → A. Dado n ∈ IN, denoto F (n) como fn . Entonces Im(F ) = A = {f0 , f1 , f2 , . . . , fn , . . .} Voy a construir una función total que no está en A. Sea g : IN → IN n 7→ fn (n) + 1 g es total porque todas las fn lo son. Para todo n, g(n) 6= fn (n), por tanto para todo n, g 6= fn . (Consigo g 6= f0 g 6= f1 ... g 6= fn ...

usando g(0) usando g(1) ... usando g(n) ...

Luego g 6∈ {f0 , f1 , f2 , . . . , fn , . . .} = A. (lema) El teorema se demuestra por reducción al absurdo como en el caso de [0, 1]. Teorema 1.27 Dado un alfabeto Σ, el conjunto de las funciones totales de Σ∗ en Σ∗ no es numerable. Dem. Análoga a la anterior. Corolario 1.28 Dado un alfabeto Σ, el conjunto de las funciones de Σ∗ en Σ∗ no es numerable. Hemos visto que el conjunto de todos los programas s´ı es numerable. En el cap´ıtulo siguiente formalizaremos la idea de que cada programa calcula una función (a cada entrada le hace corresponder una salida). De momento ya sabemos un hecho importante: Corolario 1.29 Existen funciones que no se pueden calcular con ning´ un programa.


19

EJERCICIOS 1.1. Sea f : Q × Q → Q una función definida por f (a, b) = a/b. ¿Es f total? ¿Cuál es el dominio de f ? ¿Cuál es su imagen? 1.2. Demostrar la Proposición 1.1 usando inducción. 1.3. Demostrar la Propiedad 1.18: si A ⊆ B y B es numerable, entonces A es también numerable (utilizar la definición original de numerable, esta es una propiedad básica de la que se deducen otras definiciones equivalentes). 1.4. Dados dos conjuntos numerables A y B, demostrar que A × B, el producto cartesiano de A y B, es numerable (Propiedad 1.21). 1.5. Demostrar que el conjunto de los subconjuntos finitos de IN es numerable. 1.6. Demostrar que el conjunto de las funciones de IN en IN con dominio finito es numerable. 1.7. Estudiar la demostración vista en clase de que R, el conjunto de los n´ umeros reales, no es numerable. ¿Por qué no sirve una demostración similar para demostrar que Q, el conjunto de lo n´ umeros racionales, no es numerable? 1.8. Demostrar que el conjunto de los subconjuntos de IN no es numerable. 1.9. Demostrar que el conjunto de los lenguajes sobre un alfabeto Σ no es numerable. 1.10. Demostrar que el conjunto de las funciones totales de IN en {0, 1} no es numerable. 1.11. Demostrar que el conjunto de las funciones de IN en IN con imagen finita no es numerable. 1.12. Demostrar que si {A1 , A2 , A3 , . . .} es una colección numerable de conjuntos numerables disjuntos, entonces [ i∈IN

Ai


es un conjunto numerable.

20

Cap´ıtulo 2

Problemas y datos. Un modelo abstracto de c´ alculo: la m´ aquina de registros Referencia: Cap´ıtulo 1 de [Cu80]. Comenzaremos este tema modelizando problemas mediante objetos formales (lenguajes o funciones) para un tratamiento formal posterior. Después definiremos el modelo de cálculo que utilizaremos el resto del curso, la máquina de registros con sus programas.

2.1.

Problemas, lenguajes y funciones

2.1.1.

Problemas decisionales y funcionales

Quizá la manera más fácil de analizar las diferentes componentes de la definición de un problema es mediante ejemplos. Empezaremos con un problema clásico de la teor´ıa de grafos. (Recordemos que un grafo dirigido G = (V, A) es un conjunto de vértices V y un conjunto de aristas A ⊆ V × V . Para un grafo de n vértices tomaremos siempre como conjunto de vértices V = {1, 2, 3, . . . , n}.) Ejemplo 2.1 Accesibilidad de grafos (GAP): Dado un grafo dirigido G = (V, A) y dos vértices u, v ∈ V , determinar si existe un camino de u a v en G. 21

CAPÍTULO 2. PROBLEMAS Y DATOS. UN MODELO ...

22

En el enunciado del problema se pregunta si se satisface o no una propiedad. A este tipo de problemas les denominaremos problemas decisionales. En un problema decisional se define un conjunto de datos, los datos de entrada y una propiedad. Un segundo tipo de enunciado de problema pide la construcción de un objeto, o el cálculo de un valor. Ejemplo 2.2 true gates (TG): Dado un circuito booleano, y una asignación de valores a sus entradas, calcular el n´ umero de puertas que eval´ uan a uno. Ejemplo 2.3 Camino (PATH): Dado un grafo dirigido G = (V, A) y dos vértices u, v ∈ V , calcular un camino de u a v en G. Este problema no está especificado completamente, pues puede haber más de un camino. Podemos decir, por ejemplo, “calcular el primer camino, por orden alfabético”. A los problemas en cuyo enunciado se pide la construcción de un objeto (en caso de que exista) o el cálculo de un valor, les denominaremos problemas funcionales. Un problema decisional se define a partir de un conjunto de datos E, que denominamos conjunto de entradas, y una propiedad R. Se expresa como: Dado x ∈ E, ¿se satisface R(x)? Un problema funcional se define a partir de dos conjuntos de datos E, conjunto de entradas, y S, conjunto de salidas, junto con una propiedad Q y se expresa como: Dado x ∈ E, calcular y ∈ S para el que se cumple Q(x, y). Para una entrada x, el n´ umero de objetos y que verifican Q(x, y) es 1 ó 0. En nuestros ejemplos GAP y PATH, el conjunto de entradas E es el conjunto {(G, u, v) | G es un grafo dirigido y u y v son vértices de G} 2.1.2.

Representaci´ on de datos, tama˜ no

Analicemos un poco más a fondo los conjuntos de datos. Nos interesan los problemas en los que cada dato es representable mediante una estructura de datos finita. En los problemas que hemos planteado hasta


23

ahora, se cumple este requisito, es fácil dise˜ nar una estructura de datos para las entradas. Por supuesto que la estructura nunca será u ńica, pero dise˜ narla es el primer paso en el dise˜ no de un algoritmo. Si a alto nivel requerimos que los conjuntos de datos sean representables mediante estructuras de datos, a bajo nivel queremos representarlos mediante una cadena de caracteres. A este proceso lo llamaremos codificación. A través de la codificación podemos asociar a cada dato un tama˜ no, la longitud de la cadena de caracteres que lo representa. Dado un conjunto de datos D utilizaremos la siguiente notación: x es un elemento de D representado mediante una estructura de datos. hxi es la cadena de caracteres que codifica a x, |x|, el tama˜ no de x, es la longitud de hxi. Por ejemplo la representación usual de un n´ umero natural es en binario, con lo que si la tomamos como la codificación sobre el alfabeto Σ = {0, 1} tenemos que para un n´ umero natural x, |x| = log x + 1. Como hxi es x en binario en este caso no haremos distinción entre hxi y x. Nota: Denotamos por log el logaritmo en base 2 por defecto, es decir blog2 c, con valor m´ınimo 1. Para representar un grafo G = (V, A) con vértices V = {1, . . . , n} podemos utilizar una estructura de datos consistente en una matriz booleana M definida como sigue: (

M (i, j) =

1 si (i, j) ∈ A 0 si (i, j) 6∈ A

A bajo nivel la codificación de esta matriz puede ser escribir la matriz por filas, obteniendo as´ı una cadena sobre el alfabeto {0, 1}. El tama˜ no de un grafo G será en este caso el cuadrado del n´ umero de vértices. En general, a una codificación le pediremos que sea “razonable” queriendo expresar con ello que no debe engordar artificialmente el tama˜ no de los objetos que codifica. Además deben existir algoritmos eficientes que permitan pasar de la estructura de datos x a su codificación hxi, reconocer si una cadena codifica una estructura de datos, y pasar de una cadena hxi a la estructura de datos que codifica x.


24

Podemos codificar una estructura de datos formada a partir de tipos de datos elementales a partir de las codificaciones de los mismos. Por ejemplo la entrada de PATH formada por un grafo dirigido G y dos vértices u, v podemos codificarla a partir de la codificación de G, X ∈ {0, 1}∗ , y las codificaciones en binario de u y v, Y, Z ∈ {0, 1}∗ . Una forma simple de hacer esto es a˜ nadir un s´ımbolo nuevo # para separar las componentes, por ejemplo si X = 001110000, u = 1, v = 2 la entrada G, u, v se codificar´ıa como 001110000#1#10 sobre el alfabeto {0, 1, #}. Con esta codificación el tama˜ no de la entrada (G, u, v) es |G|+|u|+|v|+2. En el mismo ejemplo, si queremos codificar entradas de la forma G, u, v sobre el alfabeto {0, 1}, podemos hacerlo a partir de la codificación anterior con tres s´ımbolos, simplemente asociando al s´ımbolo 0 la palabra 00, al 1 la palabra 01 y al # la palabra 11. Con la misma entrada que en el párrafo anterior obtenemos ahora 0000010101000000001101000100. Con esta codificación el tama˜ no de la entrada (G, u, v) es 2(|G|+|u|+|v|+2). Ejercicio. Buscar otras posibles codificaciones de entradas formadas por varios datos elementales tanto con el alfabeto {0, 1} como con alfabetos de más de dos s´ımbolos. 2.1.3.

Lenguajes y funciones

Fijado un alfabeto de codificación Σ (muy a menudo Σ = {0, 1}), asociaremos a cada problema decisional un lenguaje y a cada problema funcional una función. Consideremos un problema decisional Π con un conjunto de entradas E, de manera que cada elemento x ∈ E es representable mediante una cadena de caracteres hxi. Supongamos que Π está definido mediante la propiedad R, asociaremos al problema Π el lenguaje: L(Π) = {hxi | R(x)} Por ejemplo, si tenemos el problema: PRIMO: Dado un n´ umero natural n, determinar si n es primo. Asociaremos a PRIMO el lenguaje: L(PRIMO) = {n | n es un n´ umero primo}. A cada lenguaje L le asociamos la función caracter´ıstica χL : Σ∗ →


25

{0, 1} (ya definida en el cap´ıtulo 1): (

χL (x) =

1 si x ∈ L 0 si x 6∈ L

Luego cada problema decisional lo podemos representar mediante un lenguaje o bien mediante una función total de Σ∗ en {0, 1}. Analicemos ahora un problema funcional. Supongamos que tenemos un problema funcional Π con conjunto de entradas E, conjunto de salidas S, ambos codificados sobre Σ, y Π definido mediante la propiedad Q. Asociamos a Π la función fΠ : Σ∗ → Σ∗ definida como: fΠ (hxi) = hyi tal que se cumple Q(x, y) Para una entrada x sabemos que el n´ umero de soluciones (objetos y que verifican Q(x, y)) es 1 ó 0, as´ı que la función fΠ puede no estar definida en algunos puntos.

2.2.

La m´ aquina de registros o ´ Random Access Machine

En el cap´ıtulo 1 hemos visto que existen funciones que ning´ un programa puede calcular. La siguiente pregunta a tratar es si dentro de estas funciones no calculables hay alguna interesante, de esto se ocupa la teor´ıa de la calculabilidad. Antes de empezar a tratar lo que se puede o no calcular con un programa, tenemos que fijar qué máquina estamos programando y qué lenguaje de programación usamos. Nos interesa un modelo de máquina y un lenguaje lo más generales posibles, es decir, que resuelvan tantos problemas como el computador más potente. De esta forma, si probamos que un problema no se puede resolver en nuestro modelo, no se podrá resolver en ning´ un computador. Nuestro modelo va a ser un modelo abstracto o ideal, en el sentido de no real. Se trata de la “Random Access Machine” (RAM), que es una máquina de registros dotada de un n´ umero ilimitado de registros. Cada registro puede almacenar un n´ umero entero de cualquier tama˜ no. (Es la no limitación en el n´ umero de registros y en el tama˜ no de los mismos lo


26

que hace que la RAM sea un modelo no real, ya que es un modelo de memoria no acotada.) Nosotros programaremos la RAM usando un lenguaje de alto nivel que representamos en una notación algor´ıtmica convencional. Dispondremos de constantes y variables de tipos elementales (naturales, enteros, reales, booleanos y cadenas de caracteres) as´ı como tipos no elementales de los que nos interesará a menudo la codificación a bajo nivel, de cara a medir el tama˜ no de los datos. Tendremos las instrucciones de asignación, condicional y bucles, as´ı como las operaciones básicas de los tipos elementales. Debemos recordar que disponemos de una cantidad de memoria ilimitada, es decir, podemos usar cualquier n´ umero de variables y no hay l´ımite en el tama˜ no de los datos que estas variables pueden almacenar. Podemos utilizar la codificación de datos descrita en 2.1.2, y asumir que todos los datos de entrada de un programase codifican como una u ńica cadena de caracteres. Es por ello que, siempre que nos convenga, asumimos que todos nuestros programas tienen un u ńico parámetro de entrada, de tipo cadena de caracteres. Este parámetro corresponde a la codificación de la entrada seg´ un se haya fijado. De esta forma, el primer paso del programa será decodificar la entrada. Por ejemplo los dos programas siguientes son esencialmente el mismo: Leer W: cadena decodificacion(W, X, Y); % % El procedimiento decodificacion decodifica W=hX, Yi Z:=X+Y; Devuelve Z; Leer X, Y:natural Z:=X+Y; Devuelve Z; Los programas tendrán un u ńico parámetro de salida de tipo cadena de caracteres que corresponderá a la codificación de la salida seg´ un se haya fijado.


2.2.1.

27

Codificaci´ on de programas

Algunos de los problemas que nos interesan tienen como entrada o parte de la entrada (o de la salida) un programa. Para resolverlos algor´ıtmicamente tendremos que representar los programas mediante una estructura de datos y a bajo nivel establecer su codificación. Para definir el tipo de datos programa simplemente utilizaremos que cada programa en nuestro lenguaje de alto nivel se puede escribir como una cadena de caracteres. Al escribir cada caracter en código ASCII tenemos la codificación del programa sobre {0, 1}. Dada w ∈ {0, 1}∗ usaremos la notación Pw para el programa con codificación w, aunque a menudo identificaremos directamente w con el programa de codificación w. Aunque a menudo identificaremos cadenas y programas, usando w para el programa Pw y siendo muy laxos en la tipificación de datos. También asociaremos a cada i ∈ IN un programa Pi . Pi es el programa que ocupa la posición i-ésima entre todos los programas por orden lexicográfico (es decir, por longitudes y dentro de cada longitud por orden alfabético). También identificaremos directamente i con el programa Pi . Notemos que de esta forma Pi está definido para todo i ∈ IN y para todo programa p existe un i ∈ IN tal que Pi = p. Además existe un programa que a partir de i ∈ IN calcula una codificación de Pi , y existe otro programa que a partir de una codificación w ∈ {0, 1}∗ calcula i ∈ IN tal que Pi = Pw . Ejercicio. Escribir un programa que a partir de i ∈ IN calcula una codificación de Pi . Escribir un programa que a partir de una codificación w ∈ {0, 1}∗ calcula i ∈ IN tal que Pi = Pw . 2.2.2.

Notaci´ on para programas

Dado un programa p y una entrada x utilizaremos la siguiente notación: p(x) ↓ El programa p con entrada x termina su ejecución y da una salida. p(x) ↑ El programa p con entrada x no acaba nunca o bien acaba pero no da salida. ϕp Función que calcula el programa p, es decir: ϕp (x) = Salida del programa p con entrada x, si p(x) ↓.


28

Luego Dom(ϕp ) = {x | p(x) ↓}. Nota: Diremos que “p(x) para” (o termina, o acaba) si p(x) ↓. Si en alg´ un momento queremos expresar el hecho “p(x) acaba pero no da salida” lo indicaremos expl´ıcitamente. Denominamos paso al tiempo de ejecución de una instrucción de alto nivel. Dado t ∈ IN, diremos que “p(x) ↓ en t pasos” si p(x) para en t pasos o menos. Si en alg´ un momento queremos expresar el hecho “p(x) ↓ en t pasos exactamente” lo indicaremos expl´ıcitamente. 2.2.3.

M´ as sobre programas

Existe un programa intérprete o simulador, simular con el siguiente perfil: ´ simular(Q:in programa; X:in cadena; EXITO:out booleano; RESULTADO:out cadena); Dados un programa p y una entrada x: ´ Si p(x) ↓ entonces simular(p, x, EXITO, RESULTADO) ↓ y da sali´ da EXITO=TRUE, RESULTADO=ϕp (x). ´ Si p(x) ↑ entonces simular(p, x, EXITO, RESULTADO) ↑. Este programa nos permite simular un programa como parte de otro programa: Leer Q, X ... ´ simular(Q, X, EXITO, RESULTADO); % % El resto sólo se ejecuta si Q(X)↓ ... Existe un programa reloj, simularConReloj, que es una versión del intérprete con control de tiempo: ´ simular(Q:in programa; X:in cadena; T:in natural; EXITO:out booleano; RESULTADO:out cadena);

´ Dados un programa p, una entrada x y un n´ umero natural t, simularConReloj(p, x, t, EXITO, quiere decir “simular p con entrada x durante tiempo t”. Para cualquier ´ p, x, t, simularConReloj(p, x, t, EXITO, RESULTADO) ↓ y se cumple:


29

´ Si p(x) ↑ entonces ∀t simularConReloj con entrada (p, x, t, EXITO, RESULTADO) ´ da salida EXITO=FALSE. Si p(x) ↓ entonces ∃t0 ∈ IN tal que ´ • si t ≥ t0 entonces simularConReloj con entrada (p, x, t, EXITO, RESULTADO) ´ da salida EXITO=TRUE, RESULTADO=ϕp (x) ´ • si t < t0 entonces simularConReloj con entrada (p, x, t, EXITO, RESULTADO) ´ da salida EXITO=FALSE. Por tanto podemos utilizar este programa para simular un programa durante un tiempo: Leer Q, X, T ... ´ simularConReloj(Q, X, T, EXITO, RESULTADO); % % esto es simular Q(X) durante T pasos; ...

Es pues muy diferente utilizar los programas simular y simularConReloj, ya que el primero puede no parar. Compara la ejecución de estos dos programas, ¿los dos ejecutan el bloque de instrucciones S? Leer Q, X Leer Q, X ´ T:=30; simular(Q, X, EXITO, RESULTA ´ simularConTiempo(Q, X, T, EXITO, RESULTADO); S; S; ... ... Compara estos otros dos: Leer Q, X Leer Q, X ´ T:=30; simular(Q, X, EXITO, RESULTADO); ´ ´ simularConTiempo(Q, X, T, EXITO, RESULTADO); Si EXITO ´ Si EXITO entonces A entonces A % % No sirve para nada poner un else. else B


30

Ejercicio. Implementar en un lenguaje de programación (por ejemplo ADA) un TAD programa que contenga los procedimientos simular y simularConReloj. Hay que empezar escribiendo dos procedimientos, el primero que devuelvan la configuración inicial (contenido de las variables al inicio de la ejecución del programa), y el segundo que a partir de una configuración (contenido de las variables y n´ umero de l´ınea en que se encuentra la ejecución) calcule la siguiente configuración.

2.3.

Definici´ on de funci´ on calculable

Terminamos el cap´ıtulo definiendo lo que entendemos por función calculable.

Definición 2.4 Sea f : Σ∗ → Σ∗ una función. Decimos que f es calculasi x ∈ Dom(f ) entonces p con entrada ble si existe un programa p tal que f = ϕp , es decir: si x 6∈ Dom(f ) entonces p(x) ↑. Es importante notar que las funciones calculables pueden ser parciales. Si x 6∈ Dom(f ) entonces el programa que calcula f , con entrada x no para (lo que quiere decir que no termina o no da salida). Ejemplos 2.5 El producto de n´ umeros naturales es una función calculable total. La división es una función calculable parcial. La función: f (x) = 1 si x(x) ↓ es calculable. El hecho de que una función sea calculable parcial no quiere decir necesariamente que el programa que la calcule funcione “mal”: Leer X, Y Si Y6= 0 entonces Devuelve X DIV Y; El programa anterior calcula la división de naturales y termina siempre (pero no siempre da salida).


31

Leer X SUMA:=0; SUMANDO:=X; EPSILON:=0,01; Mientras que SUMANDO > EPSILON hacer SUMA:=SUMA+SUMANDO; SUMANDO:=SUMANDO * X; Fmq; Devuelve SUMA; Este programa calcula una aproximación de X ≥ 1 el programa no para.

P∞

n=1

X n , si X < 1. Si

Nota: Clásicamente se utilizaba el término “función recursiva” en lugar de “función calculable”. Nosotros evitaremos el primero porque está cayendo en desuso y porque la palabra recursiva tiene demasiadas connotaciones en informática.

Cap´ıtulo 3

Problemas decidibles y semidecidibles Referencia: Cap´ıtulo 7 de [Cu80]. En el cap´ıtulo anterior hemos tratado el problema de si una función se puede calcular o no con un algoritmo, definiendo el concepto de función calculable. En este tema trataremos de problemas decisionales, es decir, con sólo dos respuestas posibles. En el cap´ıtulo anterior ya hemos identificado problemas decisionales con lenguajes o conjuntos de palabras. Estudiaremos en este cap´ıtulo los conjuntos o problemas decidibles, que corresponden a problemas decisionales resolubles por medio de algoritmos, y los problemas o conjuntos semidecidibles, que representan un concepto menos restrictivo. Nota: Existe una notación anterior que no utilizaremos, que habla de lenguages “recursivos” y “enumerables recursivamente”.

3.1.

Definici´ on y primeros ejemplos de conjunto decidible

Definición 3.1 Sea A ⊆ Σ∗ un conjunto de cadenas o lenguaje. A es decidible si existe un programa p que cumple: 1. Para todo x, p(x) ↓ 32

CAPÍTULO 3. PROBLEMAS DECIDIBLES Y SEMIDECIDIBLES

33

2. Si x ∈ A, entonces ϕp (x) = 1. 3. Si x 6∈ A, entonces ϕp (x) = 0. Es decir, un programa que resuelve completamente el problema de pertenencia a A. También se dice problema decidible refiriéndose al siguiente problema correspondiente a un conjunto decidible A: Dada x, ¿x ∈ A? Un problema o conjunto indecidible es un problema o conjunto que no es decidible. Conocemos m´ ultiples ejemplos de conjuntos decidibles: los lenguajes regulares, que se vieron el curso pasado y que se pueden resolver con programas que usan memoria constante, el problema de saber si un n´ umero natural es primo, resoluble con un algoritmo que pruebe exhaustivamente todos los posibles divisores. Vamos a estar interesados en conjuntos relacionados con el comportamiento de los programas, especialmente con si paran o no. Durante este y los próximos cap´ıtulos estudiaremos muchos conjuntos de este tipo debido a que son los más sencillos de analizar. Ejemplos 3.2 Los siguientes conjuntos son decidibles: A = {p, x, t | p(x) ↓ en t pasos o menos} A es decidible, ya que el siguiente programa resuelve A: Leer Q, X, T ´ SimularConReloj(Q,X,T,EXITO) ´ Si EXITO entonces Devuelve 1 else Devuelve 0;


34

B = {p, x, z, t | ϕp (x) = z, y la computación de p con entrada x tarda t pasos o menos} B es decidible, ya que el siguiente programa resuelve B: Leer Q, X, Z, T ´ SimularConReloj(Q,X,T,EXITO,RESULTADO) ´ Si EXITO entonces Si RESULTADO=Z entonces Devuelve 1 else Devuelve 0 Fsi; else Devuelve 0;

3.2.

El problema de parada

Existe un problema muy interesante para la teor´ıa de la calculabilidad, es el problema de, dados un programa y una entrada, ¿para el programa con esta entrada? Se trata del problema de parada o “halting problem”, estudiado por Turing en 1936. El problema de parada se identifica con el conjunto: H = {p, x | p(x) ↓} Este será nuestro primer ejemplo de conjunto no decidible o indecidible, es decir, problema decisional que no resuelve ning´ un programa. Para demostrar que H es indecidible estudiaremos primero el problema diagonal de parada, K: K = {p | p(p) ↓} Es decir, el conjunto de programas que, tomando como entrada su propia codificación, paran. Teorema 3.3 K es indecidible.


35

Dem. Por diagonalización. Para cada conjunto decidible A, construiremos x0 testigo de que A 6= K. Sea A decidible. Sea pA un programa que resuelve A. Definimos x0 como el siguiente programa: Leer Z ´ Simular(pA, Z, EXITO, RESULTADO); Si RESULTADO=0 entonces Devuelve 1; Veamos que x0 ∈ K ⇔ x0 6∈ A: Si x0 ∈ K entonces x0 (x0 ) ↓, luego ϕx0 (x0 ) = 1 y ϕpA (x0 ) = 0. Por tanto x0 6∈ A. Si x0 6∈ K entonces x0 (x0 ) ↑, luego ϕpA (x0 ) = 1. Por tanto x0 ∈ A. Luego A 6= K. Como esto es cierto para cualquier A decidible, entonces K no es decidible. Corolario 3.4 H es indecidible. Dem. Por reducción al absurdo. Si H fuera decidible, sea pH un programa que resuelve H. El siguiente programa resuelve K: Leer X ´ Simular(ph,hX,Xi,EXITO,RESULTADO); Devuelve RESULTADO; Pero esto es imposible porque K es indecidible, luego pH no puede existir.

3.3.

Definici´ on y primeros ejemplos de conjunto semidecidible

Definición 3.5 Un conjunto L es semidecidible si existe un programa p que cumple: 1. Si x ∈ A, entonces ϕp (x) = 1. 2. Si x 6∈ A, entonces ϕp (x) = 0 ó bien p(x) ↑


36

Luego para que un conjunto A sea semidecidible es suficiente que haya un programa que conteste bien en el caso x ∈ A, aunque pueda no contestar (o incluso colgarse) para alguna entrada x 6∈ A. También se dice problema semidecidible refiriéndose al problema de pertenencia a un conjunto semidecidible. De las definiciones anteriores se sigue: Propiedad 3.6 Si un conjunto A es decidible entonces A es semidecidible. Tenemos pues como ejemplos de semidecidibles todos los decidibles. Veamos algunos otros. Ejemplo 3.7 El siguiente conjunto es semidecidible: C = {p, x, z | ϕp (x) = z} C cumple la definición de semidecidible, ya que tenemos el siguiente programa: paraC: Leer Q, X, Z ´ Simular(Q,X,EXITO,RESULTADO) ´ Si EXITO AND (RESULTADO=Z) entonces Devuelve 1. Este programa no para siempre. Si p, x cumplen que p(x) ↑, entonces el programa paraC con entrada p, x, z (para cualquier z) no para. Un ejemplo importante es el problema de parada. Teorema 3.8 H es semidecidible. Dem. El siguiente programa demuestra que H es semidecidible: Leer Q, X ´ Simular(Q,X,EXITO) ´ Si EXITO entonces Devuelve 1;


37

El programa anterior da salida 1 si la entrada está en H, y no da salida o incluso no termina si la entrada no está en H. Intuitivamente este algoritmo resuelve el problema de parada “en el caso positivo” aunque hemos demostrado que no existe ning´ un programa que lo resuelva completamente. Veremos otros muchos problemas decisionales en el mismo caso, son semidecidible pero no son decidibles. Como ejercicio se puede ver la propiedad análoga para K: Teorema 3.9 K es semidecidible.

3.4.

Caracterizaciones

Vamos a estudiar a continuación caracterizaciones de los dos conceptos anteriores que utilizarán la función caracter´ıstica y los programas generadores. Nos centraremos sólo en los conjuntos infinitos, ya que los finitos son casos triviales que trataremos en el siguiente apartado. Definición 3.10 Un programa p para siempre si para cualquier entrada x, p(x) ↓ Definición 3.11 Un programa p genera un conjunto L si p para siempre y L = {ϕp (n) | n ∈ IN}. Es decir, un programa p genera un conjunto L si las salidas del programa son exactamente las cadenas de L. Teorema 3.12 Dado un conjunto A infinito, son equivalentes: 1. A es semidecidible. 2. La función ΠA es calculable, donde ΠA (x) = 1 si x ∈ A. 3. Existe un programa que genera A.


38

4. Existe un programa p que genera A sin repeticiones (es decir, para todo n, ϕp (n) 6∈ {ϕp (0), ϕp (1), . . . , ϕp (n − 1)}). 5. Existe una función calculable y biyectiva f : IN → A. 6. A es el dominio de una funci´ on calculable. 7. A es el conjunto imagen de una funci´ on calculable. 8. A es el conjunto imagen de una funci´ on calculable total. Dem. Demostraremos primero la equivalencia de 1., 2., 6. y 7., después la equivalencia de 3., 4., 5. y 8., y por u ´ltimo 1.⇒3. y 8.⇒7. 1. ⇒ 2. Por definición de semidecidible tenemos un programa p que resuelve A al menos en el caso positivo. A partir de él constru´ımos el siguiente programa que calcula ΠA : Leer X ´ Simular(p,X,EXITO, RESULTADO); ´ Si EXITO AND (RESULTADO=1) entonces Devuelve 1; 2. ⇒ 6. A = Dom(ΠA ). 6. ⇒ 7. Sea f una función calculable que cumple 6. y p un programa que calcula f . Definimos la función g: g(x) = x si x ∈ Dom(f ) Tenemos que Im(g) = Dom(f ) = A. Además g es calculable ya que la calcula el siguiente programa: Leer X ´ Simular(p,X,EXITO); ´ Si EXITO entonces Devuelve X; 7. ⇒ 1. Sea f una función calculable tal que A = Im(f ), sea p un programa que calcula f . El siguiente programa demuestra que A es semidecidible. (Como realiza varias simulaciones de p con distintas entradas hay que hacer simulaciones controladas.) Leer X T:=1;


39

TERMINADO:=FALSE; Mientras que NOT TERMINADO hacer Para Y:=0 hasta T hacer ´ SimularConTiempo(p,Y,T,EXITO,RESULTADO); ´ Si EXITO AND (RESULTADO=X) entonces TERMINADO:=TRUE; Fpara; T:=T+1; Fmq; Devuelve 1; 3. ⇒ 4. Sea p un programa que genera A. Vamos a eliminar las posibles repeticiones con el siguiente programa que con entrada n da como salida la n-ésima salida diferente que produce p. Leer N NDISTINTOS:=0; DISTINTOS:=vacio; M:=0; Mientras que (NDISTINTOS < N) hacer ´ Simular(p,M,EXITO,RESULTADO); Si NOT esta(RESULTADO,DISTINTOS) entonces NDISTINTOS:=NDISTINTOS+1; a˜ nadir(DISTINTOS, RESULTADO); Fsi; M:=M+1; Fmq; Devuelve RESULTADO; 4. ⇒ 5. Si p genera A sin repeticiones, ϕp es una función calculable, total e inyectiva, Im(ϕp ) = A. Luego ϕp es la biyección buscada de IN en A. 5. ⇒ 8. En 5., por ser f biyectiva es total, y Im(f ) = A. 8. ⇒ 3. Sea f : IN → Σ∗ una función que cumple 8., sea p un programa que calcula f . Por 8. p para siempre y A = Im(f ) = {ϕp (n) | n ∈ IN}. 1. ⇒ 3. Por definición de semidecidible tenemos un programa p que resuelve A al menos en el caso positivo. El siguiente programa genera A:


40

Leer N NGENERADOS:=0; T:=1; Mientras que (NGENERADOS < N) hacer Para Y:=0 hasta T hacer ´ SimularConTiempo(p,Y,T,EXITO,RESULTADO); ´ Si (EXITO) AND (RESULTADO=1) entonces NGENERADOS:=NGENERADOS+1; Si NGENERADOS=N entonces ULTIMO:=Y; Fsi; Fpara; T:=T+1; Fmq; Devuelve ULTIMO; 8. ⇒ 7. Inmediato. Teorema 3.13 Dado un conjunto A infinito, son equivalentes: 1. A es decidible. 2. La función χA es calculable. 3. Existe un programa p que genera A en orden y sin repeticiones (es decir, para todo n > 0, ϕp (n − 1) < ϕp (n)). Dem. 1. ⇒ 2. Al ser A decidible tenemos un programa p que resuelve A. Recordemos que la función χA está definida como: (

χA (x) =

1 si x ∈ A 0 si x 6∈ A

Luego el mismo programa p calcula χA . 2. ⇒ 3. Sea p un programa que calcula χA . Al ser una función total el programa para siempre y por tanto podemos ir enumerando en orden las entradas cuya salida es 1:


41

Leer N NELEMENTOS:=0; M:=0; Mientras que (NELEMENTOS < N) hacer ´ Simular(p,M,EXITO,RESULTADO); Si RESULTADO=1 entonces NELEMENTOS:=NELEMENTOS+1; Fsi; M:=M+1; Fmq; Devuelve RESULTADO; 3. ⇒ 1. Sea p un programa que genera A en orden y sin repeticiones. Para resolver A sólo tenemos que ir generando elementos hasta que sepamos que está el que buscamos o que ya no va a aparecer: Leer X ´ Simular(p,0,EXITO,RESULTADO); N:=1; Mientras que (RESULTADO < X) hacer ´ Simular(p,N,EXITO,RESULTADO); N:=N+1; Fmq; Si RESULTADO=X entonces Devuelve 1 else Devuelve 0; Fsi; El programa anterior para siempre.

3.5.

Propiedades elementales de los conjuntos decidibles y semidecidibles

Propiedad 3.14 Todo conjunto finito es decidible. Dem. Sea L = {a1 , . . . , ak } un conjunto finito. Para resolver el problema


42

sólo necesitamos un programa que compare la entrada con k constantes, las k palabras de L: Leer X Case X of a1 Devuelve a2 Devuelve ... ak Devuelve else Devuelve

1; 1; 1; 0;

Propiedad 3.15 Un conjunto L es decidible si y s´ olo si L es decidible. ∗ (L es el complementario de L, L = {x | x ∈ Σ ∧ x 6∈ L}.) Dem. Si p es un programa que resuelve L, el siguiente programa resuelve L: Leer X ´ simular(p,X,EXITO,RESULTADO); Si RESULTADO=0 entonces Devuelve 1 else Devuelve 0; La otra implicación es idéntica, ya que L = L. Propiedad 3.16 Si A y B son conjuntos decidibles entonces A ∪ B es decidible y A ∩ B es decidible. Dem. Tenemos p y q programas que resuelven A y B respectivamente. Los siguientes programas resuelven A ∪ B y A ∩ B respectivamente. Leer X ´ simular(p,X,EXITO,RESULTADO); ´ simular(q,X,EXITO2,RESULTADO2); Si RESULTADO=1 OR RESULTADO2=1 entonces Devuelve 1 else Devuelve 0;


43

Leer X ´ simular(p,X,EXITO,RESULTADO); ´ simular(q,X,EXITO2,RESULTADO2); Si RESULTADO=1 AND RESULTADO2=1 entonces Devuelve 1 else Devuelve 0;

Propiedad 3.17 Un conjunto A es decidible si y s´ olo si A y A son ambos semidecidibles. Dem. ⇒) Si A es decidible entonces A es decidible (propiedad 3.15). Si A y A son decidibles entonces A y A son ambos semidecidibles (propiedad 3.6). ⇐) Por ser A y A semidecidibles tenemos p y q dos programas que resuelven al menos el caso positivo de A y A, respectivamente. El siguiente programa resuelve A: Leer X T:=1; TERMINADO:=FALSE; Mientras que NOT TERMINADO hacer ´ SimularConReloj(p,X,T,EXITO,RESULTADO); ´ Si EXITO entonces Devuelve RESULTADO; TERMINADO:=TRUE; else ´ SimularConReloj(q,X,T,EXITO2,RESULTADO2); ´ Si EXITO2 entonces Devuelve 1-RESULTADO2; TERMINADO:=TRUE; Fsi; Fsi; T:=T+1; Fmq;


44

Si x ∈ A entonces p(x) ↓, luego entrará en el primer entonces (si no ha entrado antes en el segundo). Si x 6∈ A entonces q(x) ↓, luego entrará en el segundo entonces (si no ha entrado antes en el primero). Luego el programa para siempre, y la respuesta que da es siempre correcta. Esta u ´ltima propiedad confirma la intuición de que A es semidecidible si se puede resolver ¿x ∈ A ? en el caso afirmativo. Como consecuencia tenemos el siguiente resultado para H (y para cualquier otro conjunto que sea semidecidible y no sea decidible). Corolario 3.18 H no es semidecidible Dem. Sabemos que H es semidecidible pero no decidible. Si H fuera semidecidible entonces, por la propiedad anterior H ser´ıa decidible. Propiedad 3.19 Si A y B son conjuntos semidecidibles entonces A ∪ B es semidecidible y A ∩ B es semidecidible Dem. Tenemos p y q programas que resuelven al menos el caso positivo de A y B respectivamente. Los siguientes programas resuelven al menos el caso positivo de A ∪ B y A ∩ B respectivamente. Leer X T:=1; TERMINADO:=FALSE; Mientras que NOT TERMINADO hacer ´ SimularConTiempo(p,X,T,EXITO,RESULTADO); ´ Si (EXITO) AND (RESULTADO=1) entonces TERMINADO:=TRUE; Fsi; ´ SimularConTiempo(q,X,T,EXITO2,RESULTADO2); ´ Si (EXITO2) AND (RESULTADO2=1) entonces TERMINADO:=TRUE; Fsi; T:=T+1; Fmq;


45

Devuelve 1; Leer X ´ Simular(p,X,EXITO,RESULTADO); ´ Simular(q,X,EXITO2,RESULTADO2); ´ ´ Si EXITO AND EXITO2 entonces Si RESULTADO=1 AND RESULTADO2=1 entonces Devuelve 1; En ambos casos los programas anteriores dan salida en los casos que nos interesan (A∪B y A∩B respectivamente), a pesar de que los programas p y q no necesariamente paran siempre. EJERCICIOS 3.1. Dadas dos funciones calculables f y g, sea h la función h(x) = 0,

si x ∈ Dom(f ) ∪ Dom(g).

Demostrar que h es calculable. 3.2. Lo mismo que el anterior, con h definida como h(x) = 0,

si x ∈ Dom(f ) ∩ Dom(g).

3.3. Demostrar el Teorema 3.9. 3.4. Demostrar que el conjunto de los conjuntos semidecidibles es numerable. Hacer lo mismo para el conjunto de los conjuntos decidibles. 3.5.

1. ¿Existe alg´ un conjunto que no sea decidible y que contenga un subconjunto infinito decidible? 2. Demostrar que todo conjunto semidecidible e infinito tiene un subconjunto decidible infinito. (Idea: utilizar las caracterizaciones de las propiedades 3.12 y 3.13.)

3.6.

1. Demostrar por diagonalización que existe un conjunto que no es semidecidible.


46

2. Demostrar por diagonalización que no existe un programa que genere T , el conjunto de programas que para para todas las entradas. (Idea: Para cada programa p que genera A ⊆ T , definimos un programa q con ϕq (n) = ϕϕp (n) (n) + 1, que no está en A pero s´ı en T .) 3.7. Si definimos φ : Σ∗ × Σ∗ → IN como φ(x, y) = 1, si x(z) ↓ para alg´ un z ≤ y. ¿Es φ calculable? ¿Es total? 3.8. Si definimos φ como φ(x, y) = 1, si x(k) ↓ para alg´ un k > y. ¿Es φ calculable? ¿Es total? 3.9. Demostrar que toda función de dominio finito es calculable. 3.10. Demostrar que no toda función de imagen finita es calculable. 3.11. Sea f : IN → IN la función definida como f (n) =

n X

ϕi (n), si 0(n) ↓, 1(n) ↓, . . . , n(n) ↓ .

i=0

1. Demostrar que f tiene dominio finito y por tanto es calculable. 2. Demostrar que el conjunto {n, m | f (n) = m} es decidible. 3.12. Sea ψ una función calculable y A un conjunto semidecidible. Demostrar que ψ −1 (A) = {x | ψ(x) ∈ A} es semidecidible. 3.13. Sea A un conjunto semidecidible Demostrar que el conjunto B = {x | ∃y x, y ∈ A} también es semidecidible.


47

3.14. Sea A un conjunto semidecidible Demostrar que [

Dom(ϕi )

i∈A

también es semidecidible. 3.15. Demostrar que las funciones f y g definidas a continuación son calculables pero no tienen ninguna extensión calculable total. 1. f (x, y) = ϕx (y) + 1 si x(y) ↓. (Idea, por diagonalización, para cada h calculable total tomamos M un programa que calcula v(x) = h(x, x). Estudiar f (M, M ) y h(M, M ).) 2. g(x, y) = t si x(y) para en exactamente t pasos. (Idea, usar reducción al absurdo, si existe tal extensión entonces H es decidible.) 3.16. Sea f la función que con entrada x devuelve la codificación del siguiente programa Leer N Si N= x entonces Devuelve 1 else Devuelve 0; 1. ¿Es f calculable? ¿Es f total? ¿Es f inyectiva? 2. Para cada x, ¿cuánto vale la función ϕf (x) ? ¿Es calculable? ¿Es inyectiva? 3. ¿Qué se puede decir del conjunto {x, y | ϕf (x) (y) = ϕf (y) (x)}? 4. ¿Es H ∩ {f (x), x | x ∈ Σ∗ } un conjunto decidible? 3.17. Sea h la función que con entrada x devuelve la codificación del siguiente programa Leer N Si N= x entonces Devuelve 1 else repetir hasta que 1 > 2;


48

1. ¿Es h calculable? ¿Es h total? ¿Es h inyectiva? 2. Para cada x, ¿cuánto vale la función ϕh(x) ? ¿Es total? ¿Es calculable? ¿Es inyectiva? 3. ¿Qué se puede decir del conjunto {x, y | ϕh(x) (y) = ϕh(y) (x)}? 4. ¿Es H ∩ {h(x), x | x ∈ Σ∗ } un conjunto decidible?

Cap´ıtulo 4

Reducciones. El teorema de Rice Referencia: Cap´ıtulos 9.1 y 6.1 de [Cu80]. Sección 10.1 de [Jones].

4.1.

Reducciones

En este apartado formalizaremos la idea de reducir un conjunto (o problema decisional) a otro, como medio de de mostrar que un conjunto es no decidible, o bien que no es semidecidible. La idea informal de que el conjunto A se puede reducir al conjunto B se puede expresar de varias formas: 1. “Resolver A se reduce a resolver B”: a partir de un programa que resuelve B podemos construir otro que resuelve A. 2. Resolver A no es más dif´ıcil que resolver B. 3. Resolver A es tan fácil o más que resolver B. Nosotros usaremos la siguiente formalización de reducibilidad, que corresponde al tipo más sencillo: Definición 4.1 Un conjunto A es reducible a un conjunto B si existe una función f calculable y total tal que, para cada x ∈ Σ∗ x ∈ A ⇔ f (x) ∈ B 49

CAPÍTULO 4. REDUCCIONES. EL TEOREMA DE RICE

50

Es decir, f transforma la pregunta ¿x ∈ A? a ¿f (x) ∈ B? de forma que si puedo resolver ¿f (x) ∈ B? tengo resuelto ¿x ∈ A? porque sé que la respuesta es la misma. Notación: A es reducible a B lo denotaremos: A ≤m B La función f de la definición anterior es una reducción de A a B. Ejemplo 4.2 Sean H y K los conjuntos definidos en el cap´ıtulo anterior (el problema de parada y el problema diagonal de parada): K = {p | p(p) ↓} H = {p, x | p(x) ↓} Veamos que K ≤m H. Sea f : Σ∗ → Σ∗ la siguiente función: ∀p f (z) = hp, pi f es total y claramente calculable. Veamos que f es una reducción de K en H. Si p ∈ K entonces p(p) ↓ y por tanto p, p ∈ H. Si p 6∈ K entonces p(p) ↑ y por tanto p, p 6∈ H. Luego p ∈ K ⇔ f (p) ∈ H y por tanto K ≤m H. Ejemplo 4.3 Dados dos conjuntos A y B, sea A ⊕ B = {0w | w ∈ A} ∪ {1w | w ∈ B} es decir, las palabras de A con 0 delante y las palabras de B con 1 delante. Esto se denomina unión marcada de A y B. Entonces K ⊕ K = {0w | w ∈ K} ∪ {1w | w ∈ K} = {0w | w ∈ K} ∪ {1w | w 6∈ K} Veamos que K ≤m K ⊕ K y K ≤m K ⊕ K Esto se demuestra utilizando las reducciones: f (x) = 0x g(x) = 1x

(para K ≤m K ⊕ K) (para K ≤m K ⊕ K).


51

Ejemplo 4.4 Veamos que H ≤m K. Sea f : Σ∗ → Σ∗ la función: “Leer N constantes :=p; CX:=x; f (p, x) = ´ Simular(, CX, EXITO); ´ Si EXITO entonces Devuelve 5.” f es una función total y calculable calculada por el programa:

Leer Q,X RESULTADO:=CONCATENAR(“Leer N; constantes :=”,Q); RESULTADO:=CONCATENAR(RESULTADO, “; CX:=”); RESULTADO:=CONCATENAR(RESULTADO, X); ´ ´ RESULTADO:=CONCATENAR(RESULTADO, “; Simular(, CX, EXITO); Si EXITO Devuelve RESULTADO; Veamos que f es una reducción de H en K. Si p, x ∈ H entonces p(x) ↓ y por tanto ∀n f (p, x)(n) ↓, es decir, para cualquier n el programa f (p, x) para con entrada n. Por tanto f (p, x) con entrada f (p, x) para. Si p, x 6∈ H entonces p(x) ↑ y por tanto ∀n f (p, x)(n) ↑, es decir, para cualquier n el programa f (p, x) con entrada n no para. Por tanto f (p, x)(f (p, x)) ↑ (f (p, x) con entrada f (p, x) no para). Luego p, x ∈ H ⇒ f (p, x) ∈ K p, x 6∈ H ⇒ f (p, x) 6∈ K y por tanto H ≤m K.

4.2.

Propiedades elementales de las reducciones

El siguiente teorema explica el interés de las reducciones. En él se formaliza la idea de que si A ≤m B entonces A es tanto o más fácil que B. Teorema 4.5 Sean A y B dos conjuntos tales que A ≤m B. Entonces se cumple que: 1. Si B es decidible entonces A es decidible.


52

2. Si B es semidecidible entonces A es semidecidible. Dem. Sea f una reducción de A a B. 1. Como B es decidible, tenemos un programa p que resuelve B. Veamos que A es decidible dando un programa que resuelve A: Leer X Y:=f (X); ´ Simular(p,Y,EXITO,RESULTADO); Si RESULTADO=1 entonces Devuelve 1 else Devuelve 0. El algoritmo anterior para siempre ya que f es calculable total y p para siempre. Como x ∈ A ⇔ f (x) ∈ B, el algoritmo anterior resuelve A. 2. Como B es semidecidible, tenemos un programa p que resuelve al menos el caso positivo de B. Veamos que A es semidecidible dando un programa que resuelve al menos el caso positivo de A: Leer X Y:=f (X); ´ Simular(p,Y,EXITO,RESULTADO); ´ Si EXITO Si RESULTADO=1 entonces Devuelve 1. El algoritmo anterior para cuando x ∈ A y resuelve al menos el caso positivo de B ya que f es calculable total, p para cuando z ∈ B y x ∈ A ⇔ f (x) ∈ B. El teorema anterior se puede enunciar equivalentemente como: Teorema 4.6 Sean A y B dos conjuntos tales que A ≤m B. Entonces se cumple que: 1. Si A no es decidible entonces B no es decidible. 2. Si A no es semidecidible entonces B no es semidecidible. lo que nos servirá para demostrar que algunos conjuntos son indecidibles o no son semidecidibles.


53

Ejemplo 4.7 Sea A el conjunto: A = {x | ϕx es inyectiva y Dom(ϕx ) 6= ∅} Veamos que K ≤m A. Sea f : Σ∗ → Σ∗ la función: “Leer N constante :=p; f (p) = ´ Simular(, , EXITO); ´ Si EXITO entonces Devuelve N.” f es claramente total y calculable. Veamos que es la reducción que buscamos: p ∈ K ⇒ p(p) ↓⇒ f (p) es un programa que calcula la identidad, ∀n ϕf (p) (n) = n ⇒ ϕf (p) es inyectiva, Dom(ϕf (p) ) = Σ∗ ⇒ f (p) ∈ A. p 6∈ K ⇒ p(p) ↑⇒ f (p) es un programa que no para para ninguna entrada, ϕf (p) tiene dominio vac´ıo ⇒ f (p) 6∈ A. Luego K ≤m A. Utilizando el teorema 4.6 (que es el mismo que el 4.5), como sabemos que K no es decidible (teorema 3.3) sabemos que A no es decidible. El siguiente teorema demuestra que los conjuntos decidibles son reducibles a todos los conjuntos. Intuitivamente esto quiere decir que seg´ un el orden marcado por las reducciones ≤m los conjuntos decidibles son los más fáciles. Teorema 4.8 Sea A un conjunto decidible. Sea B un conjunto cualquiera tal que B 6= ∅ y B 6= Σ∗ . Entonces A ≤m B Dem. Por ser B 6= ∅ y B 6= Σ∗ sabemos que existen palabras dentro y fuera de B. Fijamos b0 ∈ B y b1 6∈ B. La función (

f (x) =

b0 b1

si x ∈ A si x ∈ 6 A

es total y calculable ya que la calcula el siguiente algoritmo, donde p es un programa que resuelve A:


54

Leer X ´ SIMULAR(p, X, EXITO, RESULTADO); Si RESULTADO=1 entonces Devuelve b0 else Devuelve b1 . (En este algoritmo b0 y b1 son constantes.) f es claramente una reducción de A en B. La reducción ≤m es transitiva: Teorema 4.9 Si A ≤m B y B ≤m C entonces A ≤m C. Dem. Sea f una reducción de A en B y g una reducción de B en C. Entonces la composición de f y g, g ◦ f (x) = g(f (x)) es una reducción de A a C, ya que es calculable total (por serlo f y g) y cumple: x ∈ A ⇔ f (x) ∈ B ⇔ g(f (x)) = g ◦ f (x) ∈ C. Vamos a ver a continuación que H y K están entre los más dif´ıciles de los conjuntos semidecidibles. Definición 4.10 Dado un conjunto o clase de conjuntos C, un conjunto X ∈ C es completo para C si para todo A ∈ C, A ≤m X. Teorema 4.11 H es completo para la clase de los conjuntos semidecidibles, es decir, si A es un conjunto semidecidible entonces A ≤m H. Dem. Sea A un conjunto semidecidible. Sea p un programa que resuelve al menos el caso positivo de A. Existe un programa que resuelve al menos el caso positivo de A y sólo da salida para las entradas en A: x0 : Leer X ´ Simular(p, X, EXITO, RESULTADO); ´ Si EXITO entonces Si RESULTADO=1 entonces Devuelve 1. Sea f : Σ∗ → Σ∗ la función: f (z) = x0 , z f es claramente una función total y calculable calculada por el programa:


55

Leer Z Devuelve x0 , Z. (x0 es una constante del programa.) Veamos que f es una reducción de A en H. z ∈ A ⇒ ϕx0 (z) = 1 ⇒ x0 (z) ↓⇒ f (z) = x0 , z ∈ H z 6∈ A ⇒ x0 (z) ↑⇒ f (z) = x0 , z 6∈ H

Por la transitividad tenemos: Corolario 4.12 Sea X un conjunto semidecidible y sea C un conjunto completo para los semidecidibles. Si C ≤m X entonces X es completo para la clase de los conjuntos semidecidibles. Dem. Sea A un conjunto semidecidible. Como sabemos que A ≤m C y por hipótesis C ≤m X, aplicando transitividad (teorema 4.9) tenemos que A ≤m X. Con los dos u ´ltimos resultados tenemos: Corolario 4.13 K es completo para la clase de los conjuntos semidecidibles. Dem. H ≤m K (ejemplo 4.4) y H es completo para los semidecidibles (teorema 4.11), luego por el corolario anterior K es completo para los semidecidibles. Nota: Las reducciones que utilizaremos en los problemas serán a menudo reducciones desde H o desde H. Además serán casi todas de unos de los dos tipos que inclu´ımos a continuación. Definimos las funciones f1 y f2 como: “Leer N constante :=p; CX:=x; ´ f1 (p, x) = Simular(, CX, EXITO); ´ Si EXITO entonces ´ CODIGO1.”


56

“Leer N constante :=p; CX:=x; ´ SimularConTiempo(, CX, N, EXITO); ´ entonces f2 (p, x) = Si EXITO ´ CODIGO1 else ´ CODIGO2.” Veamos cómo funcionaran f1 y f2 como reducciones desde H: ´ p, x ∈ H ⇒ p(x) ↓⇒ f1 (p, x) es un programa que ejecuta CODIGO1. p, x 6∈ H ⇒ p(x) ↑⇒ f1 (p, x) es un programa que no para para ninguna entrada, ϕf1 (p,x) tiene dominio vac´ıo. p, x ∈ H ⇒ p(x) ↓⇒ ∃n0 tal que p con entrada x tarda exactamente tiempo n0 , luego f2 (p, x) es un programa que con entrada n < n0 ejecuta ´ ´ CODIGO2 y con entrada n ≥ n0 ejecuta CODIGO1. ´ p, x 6∈ H ⇒ p(x) ↑⇒ f2 (p, x) es un programa que ejecuta CODIGO2. ´ ´ Eligiendo adecuadamente CODIGO1 y CODIGO1 podemos tener gran variedad de reducciones, como veremos en los problemas.

4.3.

Conjuntos de ´ındices, teorema de Rice

Hasta ahora hemos visto dos tipos de demostraciones de que un conjunto no es decidible: la que utilizamos para el problema de parada, basada en diagonalización, y las demostraciones del apartado anterior basadas en reducciones desde un conjunto indecidible utilizando el teorema 4.5. Vamos a ver ahora un tercer método que sirve exclusivamente para los conjuntos que llamaremos conjuntos de ´ındices, que nos servirá para ahorrarnos unas cuantas reducciones. Definición 4.14 Sea f una función. Llamaremos conjunto de ´ındices de f al siguiente conjunto: IND(f ) = {p | ϕp ≡ f } Es decir, el conjunto de ´ındices de una función f está formado por todos los programas que calculan f .


57

Por supuesto, si f no es calculable entonces IND(f ) = ∅. Ejercicio: Demostrar que si f es una función calculable entonces IND(f ) es infinito. Definición 4.15 Sea F un conjunto de funciones. Llamaremos conjunto de ´ındices de F a: IND(F ) =

[

IND(f ) = {p | ϕp ∈ F }

f ∈F

es decir, el conjunto de los programas que calculan una función de F . Definición 4.16 Sea A un conjunto. Diremos que A es un conjunto de ´ındices si existe un conjunto de funciones F tal que A = IND(F ). En otras palabras, si un conjunto es un conjunto de ´ındices y contiene un programa que calcula una función contiene todos los programas que la calculan, y viceversa, si no contiene uno no contiene ninguno. La siguiente propiedad se deja como ejercicio: Propiedad 4.17 Sea A un conjunto. A es un conjunto de ´ındices si y sólo si [ INDϕx ⊆ A x∈A

A continuación veremos que ning´ un conjunto de ´ındices no trivial es decidible. Teorema 4.18 Teorema de Rice. Sea A un conjunto de ´ındices con A 6= ∅ y A 6= Σ∗ . Entonces A es indecidible. Dem. Vamos a ver que se cumple al menos una de las dos siguientes afirmaciones: 1. H ≤m A 2. H ≤m A Si demostramos 1., como H no es decidible, A no puede serlo tampoco. Si demostramos 2., como H no es decidible, A tampoco. Sea v la función de dominio vac´ıo, función que calculan los programas que no paran para ninguna entrada. Como A es un conjunto de ´ındices, tenemos dos casos posibles:


58

1. IND(v) ∩ A = ∅. En este caso demostraremos que H ≤m A. 2. IND(v) ⊆ A. Aqu´ı demostraremos que H ≤m A. Caso 1: Si IND(v)∩A = ∅, sea g una función calculable tal que IND(g) ⊆ A (g existe porque A 6= ∅ y es un conjunto de ´ındices), sea w0 un programa que calcula g. Definimos α la siguiente función: “Leer N constante :=p; CX:=x; ´ Simular(,CX,EXITO); α(p, x) = ´ Si EXITO entonces ´ Simular(w0 ,N,EXITO2,RESULTADO2); ´ Si EXITO2 entonces Devuelve RESULTADO2.” Veamos que α es una reducción de H en A. Si p(x) ↓, α(p, x) es un programa que calcula g. Si p(x) ↑ entonces α(p, x) es un programa que no para con ninguna entrada, luego calcula v. Por tanto p, x ∈ H ⇒ α(p, x) ∈ IND(g) ⇒ α(p, x) ∈ A p, x 6∈ H ⇒ α(p, x) ∈ IND(v) ⇒ α(p, x) 6∈ A Luego en este caso H ≤m A. Caso 2: Si IND(v) ⊆ A, sea f una función calculable tal que IND(f ) ∩ A = ∅ (f existe porque A 6= Σ∗ y es un conjunto de ´ındices), sea w1 la codificación de un programa que calcula f . Definimos β la siguiente función: “Leer N constante :=p; CX:=x; ´ Simular(,CX,EXITO); β(p, x) = ´ Si EXITO entonces ´ Simular(w1 ,N,EXITO2,RESULTADO2); ´ Si EXITO2 entonces Devuelve RESULTADO2.” Veamos que β es una reducción de H en A. Si p(x) ↑ entonces β(p, x) es un programa que no para con ninguna entrada, luego calcula v. Si p(x) ↓, β(p, x) es un programa que calcula f . Por tanto p, x ∈ H ⇒ β(p, x) ∈ IND(v) ⇒ β(p, x) ∈ A p, x 6∈ H ⇒ β(p, x) ∈ IND(f ) ⇒ β(p, x) 6∈ A


59

Luego en este caso H ≤m A. Como corolario al caso 2 de la demostración anterior tenemos: Corolario 4.19 Sea A un conjunto de ´ındices con A 6= ∅ y A 6= Σ∗ y tal que A contiene un programa que calcula la funci´ on vac´ıa. Entonces A no es semidecidible. Dem. Esto es consecuencia de la demostración anterior, ya que este caso, IND(v) ⊆ A, demostramos que H ≤m A. ¿Cuándo podemos utilizar el teorema de Rice para demostrar que un conjunto no es decidible? Cuando dicho conjunto es un conjunto de ´ındices, es decir, cuando el hecho de que p esté o no en el conjunto sólo depende de quién es ϕp . Sea L = {x | ϕx es inyectiva}. L es el conjunto de Ejemplos 4.20 ´ındices de F = {f | f es inyectiva}. L 6= ∅ ya que existen funciones calculables e inyectivas, por ejemplo la función identidad ident(x) = x ∀x. L 6= Σ∗ ya que existen funciones calculables no inyectivas, por ejemplo una función constante f (x) = 0 ∀x. Luego por el teorema de Rice, L no es decidible. No se puede usar Rice para el siguiente conjunto L = {x | ϕx (x) = 1} ya que no es un conjunto de ´ındices, porque pueden existir dos programas x 6= y que calculan la misma función f y tales que f (x) = 1, f (y) 6= 1. Tanto x como y están en IND(f ), pero x ∈ L y y 6∈ L. Luego L no es un conjunto de ´ındices. Tampoco se puede usar para K = {p | p(p) ↓} ya que pueden existir dos programas x, y que calculen la misma función f , con f (x) definida y f (y) indefinida. En este caso x ∈ K, y 6∈ K, x, y ∈ IND(f ), luego K no es un conjunto de ´ındices.


60

En los dos casos anteriores el hecho de que p esté o no en el conjunto NO depende sólo de quién es ϕp , sino también de p tomado como entrada. Por tanto no se puede aplicar Rice. Cuando no es posible utilizar Rice, otro método para demostrar que un conjunto no es decidible son las reducciones vistas en este mismo cap´ıtulo. Ejemplo 4.21 Veamos que H ≤m L, donde L = {x | ϕx (x) = 1} Como sabemos que H no es decidible, entonces L no lo es. La reducción es “Leer N constante :=p; CX:=x; f (p, x) = ´ Simular(,CX,EXITO); ´ Si EXITO entonces Devuelve 1.” Si p, x ∈ H ⇒ p(x) ↓⇒ f (p, x) es un programa que calcula la función constante 1 ⇒ ϕf (p,x) (f (p, x)) = 1 ⇒ f (p, x) ∈ L. Si p, x 6∈ H ⇒ p(x) ↑⇒ f (p, x) es un programa que no para nunca ⇒ f (p, x)(f (p, x)) ↑ ⇒ f (p, x) 6∈ L. EJERCICIOS Decir si los siguientes conjuntos son o no decidibles, y si son o no semidecidibles. 4.1. {x | ϕx (x) = x}. 4.2. {x, y, z | ϕx (y) = z}. 4.3. {x, y, z | ϕx (z) = ϕy (z)}. 4.4. {x | ϕx es suprayectiva}. 4.5. {x | ϕx no es suprayectiva}. 4.6. {x | ϕx es inyectiva}. 4.7. {x | ϕx no es inyectiva}.


61

4.8. {x | ϕx es biyectiva}. 4.9. {x | ϕx no es biyectiva}. 4.10. {x | ϕx es total}. 4.11. {x | x no da salida para ninguna entrada}. 4.12. {x | Dom(ϕx ) es indecidible}. 4.13. {x | Dom(ϕx ) es decidible}. 4.14. {x | Dom(ϕx ) no es semidecidible}. 4.15. {x | Dom(ϕx ) es semidecidible }. 4.16. {x | Im(ϕx ) = ∅}. 4.17. {x | Im(ϕx ) es indecidible }. 4.18. {x | Im(ϕx ) es decidible }. 4.19. {x | Im(ϕx ) no es semidecidible }. 4.20. {x | Im(ϕx ) es semidecidible }. 4.21. {x, y | y ∈ Im(ϕx )}. 4.22. {x | ϕx es constante}. 4.23. {x | ϕx tiene una extensión calculable total}. Pista: usar el ejercicio 3.15. 4.24. {x, y | Dom(ϕx ) = Dom(ϕy )}. 4.25. {x | ∃t(x(t) ↓ y ϕx (t) = ϕt (t))}. 4.26. {x | Im(ϕx ) ⊆ {0, 1}}. 4.27. {x | Im(ϕx ) ⊆ {0, 1} y (∀yϕx (y) = 1 si y sólo si y(y) ↓)}. 4.28. {x | Im(ϕx ) ⊆ {0, 1} y (∀yϕx (y) = 1 ⇒ y(y) ↓)}. 4.29. {x, y | ϕx = ϕy }. 4.30. Demostrar la Propiedad 4.17.

Cap´ıtulo 5

Otros problemas indecidibles Referencia: Cap´ıtulos 6.3 de [Cu80] y 9.4 de [HMU02]. De los cap´ıtulos anteriores sabemos que los siguientes problemas son indecidibles: Dado un programa p, ¿termina p con cualquier entrada? Dados dos programas p y q, ¿calculan p y q la misma función? Dado un programa p y una entrada x, ¿para p con entrada x? A continuación enunciamos algunos problemas indecidibles históricos. Por falta de tiempo no demostraremos la indecidibilidad. Ecuaciones diofánticas. Dada una ecuación de cualquier grado con coeficientes enteros, ¿tiene dicha ecuación alguna solución entera? El problema de correspondencia de Post. Dadas dos listas de palabras de Σ∗ , A = (x1 , . . . , xn ) y B = (y1 , . . . , yn ), ¿existe una secuencia no vac´ıa de enteros (i1 , . . . , ir ) con 1 ≤ ij ≤ n para 1 ≤ j ≤ r tal que xi1 . . . xir = yi1 . . . yir . Ejemplo de entrada del problema de Post: x1 = 111 y1 = 1 x2 = 10 y2 = 10111 x3 = 0 y3 = 10 Para esta entrada la solución es SI, ya que y2 y1 y1 y3 = x2 x1 x1 x3 = 101111110 62

Cap´ıtulo 6

Otros modelos de c´ alculo: la tesis de Turing-Church Referencia: Cap´ıtulos 2 y 3 de [Cu80]. Hemos definido en los cap´ıtulos anteriores el concepto de función calculable por un programa de nuestro modelo RAM (as´ı como el concepto de conjunto decidible que se puede caracterizar a partir del de función calculable). En los u ´ltimos 50 a˜ nos ha habido muchas propuestas distintas para una caracterización formal precisa de la idea informal de “lo que se puede calcular de manera automática”. La propuesta más reciente es la que hemos presentado en el cap´ıtulo 2, la máquina de registros o RAM. En este cap´ıtulo vamos a considerar algunas otras formalizaciones: Las funciones recursivas de Gödel y Kleene (1936). Las máquinas de Turing (1936). El λ-cálculo de Church (1930). De estos modelos nos interesan dos cuestiones: 1. ¿Cómo se relacionan las distintas formalizaciones entre s´ı, y en particular con la RAM? 2. ¿Con qué exactitud caracterizan estos modelos (y en particular la RAM) la idea intuitiva de calculable? 63

´ CAPÍTULO 6. OTROS MODELOS DE CALCULO: LA TESIS DE ...

6.1.

64

Las funciones recursivas de G¨ odel y Kleene

Gödel y Kleene definen expl´ıcitamente qué funciones son calculables, es decir, dan una definición independiente de un modelo de cálculo concreto. Veremos que su definición coincide con la nuestra de función calculable. En esta sección trabajamos con funciones de INn en IN (n ≥ 1). Veamos primero tres formas de construir unas funciones a partir de otras. Sea x = (x1 , . . . , xn ). 1. Dadas las funciones f (y1 , . . . , yk ), g1 (x ), g2 (x ), . . . gk (x ) la sustitución de g1 , . . . , gk en f es la función h: h(x ) = f (g1 (x ), g2 (x ), . . . gk (x )) 2. Dadas las funciones f (x ), g(x , y, z) la recursión de f y g es la función h: h(x , 0) = f (x ) h(x , y + 1) = g(x , y, h(x , y)) 3. Dada la función f (x , y), la minimalización de f es la función h tal que h(x ) = el m´ınimo y tal que (i) f (x , y) = 0, (ii) f (x , z) está definido, para todo z ≤ y, si existe tal y. indefinida, en otro caso (h es una versión fuerte de “el menor y tal que f (x , y) = 0”). Ejemplos 6.1

La función h h(x, 0) = x+1 h(x, y + 1) = x + h(x, y)

es la recursión de f (x) = x + 1, g(x, y, z) = x + z.


65

La función h h(0) = 1 h(y + 1) = y · h(y) es la recursión de f ≡ 1, g(y, z) = y · z. Dado p(x) un polinomio de coeficientes enteros, la función h(z) =

“la menor raiz entera de p(x) − z (si existe tal raiz)”

es la minimalización de f (z, x) = p(x) − z. A continuación damos la definición de funciones recursivas de Gödel y Kleene. Definición 6.2 El conjunto de las funciones recursivas de Gödel y Kleene es el menor conjunto que contiene las siguientes funciones: 1. La función constante 0: 0(n) = 0 ∀n. 2. La función sucesor s(n) = n + 1 ∀n. 3. Para cada n ∈ IN, i ≤ n, la función de proyección i-ésima Uin definida como: Uin (x1 , . . . , xn ) = xi y es cerrado por las operaciones de sustitución, recursión y minimalización. Nota: Un conjunto A es cerrado por una operación ∗ si para todo f, g ∈ A se cumple que f ∗ g ∈ A. Esta definición de función recursiva de Gödel y Kleene dada es formalista, no usa ning´ un modelo de cálculo sino que a partir de unas funciones elementales (1., 2. y 3.) se construyen todas las funciones recursivas de Gödel y Kleene usando sustitución, recursión y minimalización. Ejemplos 6.3 Algunas funciones recursivas de Gödel y Kleene: La función suma, obtenida como recursión de U11 y la función sucesor: suma(n, 0) = U11 (n) suma(n, m + 1) = s(U33 (n, m, suma(n, m)))


66

La función suma de 3, obtenida aplicando la sustitución a la anterior: h(x, y, z) = suma(x, suma(y, z)) = suma(U13 (x, y, z), suma(U23 (x, y, z), U33 (x, y, z))) La función predecesor p(m + 1) = m, p(0) = 0 puede obtenerse como p(m) = h(0, m) con h: h(n, 0) = 0(n) h(n, m + 1) = U23 (n, m, h(n, m)) ˙ = máx(x − y, 0) obtenida como recursión de U11 y La función x−y la función predecesor: ˙ n−0 = U11 (n) ˙ ˙ n−(m + 1) = p(U33 (n, m, n−m)) Si f es recursiva de Gödel y Kleene, inyectiva y total, la función f −1 (y) = x con f (x) = y obtenida por minimalización de h: ˙ (x)) + (f (x)−y) ˙ h(y, x) = (y −f Veamos que la definición de función recursiva de Gödel y Kleene coincide con nuestra definición de función calculable, dada en el cap´ıtulo 2. Teorema 6.4 Una función f es recursiva de G¨ odel y Kleene si y s´ olo si es calculable. Dem. (esquema) (Parte I) Demostramos que las funciones recursivas de Gödel y Kleene son calculables: Una función h recursiva de Gödel y Kleene se obtiene aplicando a funciones básicas (0(x), s(x), Uin (x1 , . . . , xn )) un n´ umero finito de veces t, operaciones de sustitución, recursión y minimalización. Por inducción sobre t, el n´ umero de operaciones aplicadas: 1. t = 0. Se trata de una de las funciones básicas, para cualquiera de ellas podemos construir fácilmente un programa que la calcula.


67

2. Paso de inducción, t > 0. Hay tres casos: (a) h es la sustitución de g1 (x1 , . . . , xn ), . . . , gk (x1 , . . . , xn ) en f , y cada una de las funciones g1 , . . . , gk , f se obtiene aplicando menos de t operaciones. Por hipótesis de inducción, las funciones g1 , . . . , gk , f son calculables, y existen programas p1 , . . . , pk , q que calculan respectivamente g1 , . . . , gk , f . Utilizando estos programas y siguiendo la definición de h, tenemos un programa para h (nótese que n es un valor fijo): Leer X1 , . . . , Xn Para I:=1 hasta k hacer AI := ϕpI (X1 , . . . , Xn ); Devuelve ϕq (A1 , . . . , Ak ). Por tanto h es calculable. (b) Los casos en que h es la recursión de dos funciones f y g, ó h es es la minimalización de una función f se demuestran análogamente al caso (a), utilizando la hipótesis de inducción y la programación de dichas operaciones. (Parte II) Esquema de la demostración de que las funciones calculables son recursivas de Gödel y Kleene: Sea h una función calculable calculada por un programa p. Definimos dos funciones auxiliares c(x, t) = “contenido del registro de salida depués de t pasos de p con entrada x”. j(x, t) = “n´ umero de la instrucción ejecutada en el paso t de p con entrada x (vale 0 si p con entrada x termina antes)” Notemos que la minimalización de j(x, t) es el tiempo que tarda el programa p con entrada x. Si llamamos f (x) a esa minimalización, h(x) = c(x, f (x)). La demostración se completa demostrando que tanto c como j son funciones recursivas de Gödel y Kleene. Debido a la equivalencia de esta definición con la de función calculable basada en el modelo RAM, podemos asegurar que todo programa es equivalente a un n´ umero finito de aplicaciones de los operadores sustitución, recursión y minimalización.


6.2.

68

Las m´ aquinas de Turing

Una máquina de Turing, abreviadamente TM, es un autómata finito con una cinta infinita adicional. La cinta está dividida en celdas, la máquina accede a la información de la cinta a través de una cabeza lectora/escritora que puede leer/escribir sobre una u ńica celda cada vez. La cabeza se puede mover a derecha o izquierda, pero sólo una posición cada vez.

Una transición de una máquina de Turing depende del estado en que está la máquina y del contenido de la cabeza lectora, seg´ un estos se realizarán las siguientes tres acciones: cambio de estado, escritura en la celda sobre la que está la cabeza, movimiento de la cabeza. Inicialmente, la posición más a la izquierda de la cinta contiene un carácter especial .. A partir de esta posición contiene la palabra de entrada. El resto de la cinta contiene en todas las celdas un carácter especial denominado blanco, al que representaremos con el signo b. itiremos tres tipos de movimientos para la cabeza: celda a la derecha, celda a la izquierda y no moverse. Si la cabeza está en la posición más a la izquierda de la cinta y se pide un movimiento a la izquierda, la cabeza no se moverá. La definición formal de una máquina de Turing es: Definición 6.5 Una máquina de Turing es una estructura (Q, Σ, Γ, δ, q0 ), donde Q es un conjunto finito de estados,


69

Σ es un alfabeto, el alfabeto de entrada, Γ = Σ ∪ {., b} es el alfabeto de cinta (b,. 6∈ Σ), δ : Q × Γ → Q × Γ × {i, d, n} es una función de transición, q0 es el estado inicial (q0 ∈ Q), La función de transición especifica, dado el estado actual y el s´ımbolo que lee la cabeza, el nuevo estado, el nuevo s´ımbolo de dicha posición y un movimiento de la cabeza. Inicialmente la máquina se encuentra en el estado q0 , con una palabra w ∈ Σ∗ escrita en la parte izquierda de la cinta, precedida por el s´ımbolo ., y la cabeza sobre la segunda celda de la cinta (primer s´ımbolo de w). La máquina ejecuta transiciones mientras pueda aplicar la función de transición. Si en alg´ un momento la máquina se encuentra en un estado q con carácter a en la cabeza y no hay transición definida para el par (q, a), entonces la máquina para. Nota: Existen varias definiciones equivalentes de máquina de Turing que pueden encontrarse en la literatura. Por ejemplo se pueden definir máquinas de Turing con dos (o más) cintas, en ese caso la entrada se escribe u ńicamente en la primera cinta, inicialmente todas las cabezas de cinta están sobre la segunda celda, y la función de transición es de la forma: δ : Q × Γ × Γ → Q × Γ × {i, d, n} × Γ × {i, d, n} Utilizaremos la siguiente notación: M (w) ↓ representa que la TM M con entrada w para. M (w) ↑ representa que la TM M con entrada w no para. M (w) representa el contenido de la cinta desde el carácter . hasta el primer blanco, después de que M con entrada w ha parado (si M (w) ↓). Definición 6.6 La función calculada por una TM M , denotada por ϕM , se define como: ϕM (w) = M (w) si M (w) ↓ Dada una función f : Σ∗ → Σ∗ diremos que M calcula f si f = ϕM .


70

Ejercicio. Dise˜ nar máquinas de Turing que calculen la función identidad y la función sucesor para n´ umeros naturales codificados en binario. Cada máquina de Turing calcula una función. ¿Cómo se comparan estas funciones con las calculables? La respuesta es el siguiente teorema. Teorema 6.7 Una función es calculable si y s´ olo si existe una m´ aquina de Turing que la calcula. Dem. (idea) Para la implicación de derecha a izquierda, dada una máquina de Turing M es fácil construir un programa que la simule. Dicho programa calculará la misma función que M . Para la otra implicación se utiliza la caracterización de las funciones calculables como funciones recursivas de Gödel y Kleene.

6.3.

El λ-c´ alculo de Church

El λ-cálculo es un modelo en el que se trabaja con expresiones que se transforman mediante una u ńica operación, la reescritura. Definición 6.8 Sea A un conjunto finito, el conjunto de las variables. Llamamos λ-expresión a e, una palabra sobre A ∪ {λ, [, ]} que cumple una de las siguientes condiciones: e ∈ A, e = [f g], donde f y g son λ-expresiones, e = λa.f , donde a ∈ A y f es una λ-expresión. Definición 6.9 Dada una λ-expresión e = [λx.P Q], e se reescribe en R si R es el resultado de sustituir x por Q cada vez que aparezca x en la expresión P . Lo denotaremos [λx.P Q] → R Ejemplos 6.10 [λx.y 3] → y

[λx.x + 2 5] → 5 + 2


71

[λx.[x x] λx.[x x]] → [λx.[x x] λx.[x x]] [λx.[λy.x + y 3] 2] → [λy,2 + y 3] → 2 + 3 Intuitivamente, interpretamos una expresión M como un programa, y ejecutar M con una entrada N es reescribir iteradamente la expresión [M N ]. La ejecución termina cuando no se puede seguir reescribiendo, es decir, cuando no aparece [λ Algunas expresiones nunca terminan de reescribirse, como la del ejemplo, [λx.[x x] λx.[x x]] Nota: (Sobre los nombres de las variables) Una λ-expresión será ilegal si contiene una subexpresión de la forma [P Q] de forma que tanto P como Q contienen una misma variable x pero P contiene λx mientras que Q no (o viceversa). Sólo itiremos expresiones donde esto no ocurre, las que llamaremos legales. Un ejemplo de expresión ilegal es [λx.y λu.[x u]], la x aparece precedida de λ en λx.y y “libre” en λu.[x u]. Podemos transformar expresiones ilegales en otras legales “similares” renombrando en la subexpresión correspondiente variables que aparecen precedidas de λ. (El ejemplo anterior pasa a [λw.y λu.[x u]]). Tampoco itiremos λ-expresiones que contengan una subexpresión de la forma [λx.P Q] de forma que P contiene λx. Por ejemplo no itiremos [λx.[λx.ya] [uv]] Para hablar de funciones que pueden calcularse en este modelo, primero hemos de definir las expresiones que representan los naturales, que se denominan naturales de Church: 0 ≡ λf.λx.x 1 ≡ λf.λx.[f x] 2 ≡ λf.λx.[f [f x]] 3 ≡ λf.λx.[f [f [f x]]] n ≡ λf.λx.[f [f [f [f . . . [f x] . . .] ([f aparece n veces) Definición 6.11 Dada una λ-expresión M , ϕM : IN → IN es la función definida como ϕM (n) = m si [M n] se reescribe a m donde dentro de las expresiones, m y n denotan el correspondiente natural de Church.


72

Definición 6.12 Una función f : IN → IN es λ-calculable si existe una λ-expresión M tal que ϕM = f . Por ejemplo, la siguiente expresión calcula la función sucesor: succ ≡ λn.λy.λz.[y [[n y] z]] [succ 1] ≡ [λn.λy.λz.[y [[n y] z]] λf.λx.[f x]] → λy.λz.[y [[λf.λx.[f x] y] z]] → λy.λz.[y [λx.[y x] z]] → λy.λz.[y [y z]] ≡ 2 Un programa que no para nunca: M ≡ λy.[λx.[x x] λx.[x x]] [M a] → [λx.[x x] λx.[x x]] →

[λx.[x x] λx.[x x]] . . .

Las siguientes expresiones representan los valores true y false. true ≡ λx.λy.x f alse ≡ λx.λy.y [[true P ]Q] ≡ [[λx.λy.x P ]Q] → [λy.P Q] → P [[f alse P ]Q] ≡ [[λx.λy.y P ]Q] → [λy.y Q] → Q La función not: not ≡ λx.[[x f alse] true] [not true] ≡ [λx.[[x f alse] true] true] → [[true f alse] true] → f alse [not f alse] ≡ [λx.[[x f alse] true] f alse] → [[f alse f alse] true] → true La función if: if ≡ λc.λp.λq.[[c p] q] Ejercicio. Reescribir [[[if A] B] C] donde A es la expresión true o la expresión false. Ejercicio. Averiguar qué funciones calculan las siguientes expresiones: zerop ≡ λn.[[n [true f alse]] true] mif uncion ≡ λx.[[[if [zerop x]] [succ x]] [[∗ x] x]] Cada λ-expresión calcula una función. El siguiente teorema nos dice que se trata de las funciones calculables. Teorema 6.13 Una funci´ on es calculable si y s´ olo si es λ-calculable.


73

Dem. (idea) Para la implicación de derecha a izquierda, dada una expresión M es fácil construir un programa que con entrada n haga la reescritura iterada de [M n]. Dicho programa calculará la misma función que M . Para la otra implicación se utiliza la caracterización de las funciones calculables como funciones recursivas de Gödel y Kleene.

6.4.

La tesis de Turing-Church

En este cap´ıtulo hemos visto el siguiente resultado general: Teorema 6.14 Los tres modelos vistos en este cap´ıtulo dan como funciones calculables las funciones calculables definidas con la m´ aquina de registros RAM. Hay otros modelos que se han ido proponiendo para caracterizar lo que se puede “computar”. Todos ellos han resultado equivalentes. Esto ha dado lugar a la siguiente tesis o conjetura: Tesis de Turing-Church. Cualquier modelo razonable de computación calcula exactamente las funciones calculables. La palabra “razonable” hace que esta tesis no sea precisa. El significado concreto es: la comunidad cient´ıfica, con los conocimientos actuales, opina que no hay ning´ un modelo de computación más potente que los conocidos (potente en el sentido de calcular más funciones). En la segunda parte del curso veremos que la situación puede variar ligeramente cuando comparamos la eficiencia de los distintos modelos. EJERCICIOS 6.1. Para cada una de las siguientes funciones, dar una máquina de Turing que la calcule. 1. Dado A = {w | w = #y, y ∈ {0, 1}∗ , y = y R }, f : {0, 1#}∗ → w 7→ w 7→

{0, 1, #}∗ # si w ∈ A indefinido, en otro caso


74

2. Dado A = {0n 1n | n ∈ IN}, f : {0, 1}∗ → w 7→ w 7→

{0, 1}∗ 1 si w ∈ A 0 en otro caso

3. Dado A = {0n 1n 0n | n ∈ IN}, f : {0, 1}∗ → w 7→ w 7→


4. Dado A = {w | w ∈ {0, 1}∗ , |w|0 = |w|1 }, f : {0, 1}∗ → w 7→ w 7→


6.2. Demostrar que las siguientes funciones son funciones recursivas de Gödel y Kleene (f.r.g.) ˙ de los Ejemplos 1. f (n, m) = m´ın(n, m) (Usar la función x−y 6.3.) 2. f (n, m) = máx(n, m) 3. f (n) = n! 4. f (n, m) = m.c.d.(n, m). (Usar el algoritmo de Euclides.) 5. La función f definida como f (0) = 1 f (1) = 1 f (n + 2) = f (n) + f (n + 1)

Cap´ıtulo 7

Complejidad y codificaci´ on Referencia: Cap´ıtulos 1 y 2 de [GJ78] En la primera parte del curso nos hemos ocupado de saber si un problema dado se puede resolver o no con un algoritmo. En ning´ un momento nos hemos preocupado de si un algoritmo que resuelve un problema concreto es eficiente o no. De esto se va a ocupar el resto de este curso: queremos saber qué problemas se pueden resolver con un algoritmo eficiente, lo que en la actualidad se identifica con un algoritmo que tarda tiempo polinómico en el tama˜ no de la entrada.

7.1.

El problema del viajante

Continuamos la presentación del tema utilizando el siguiente problema concreto. Dado un n´ umero n ∈ IN que representa el n´ umero de ciudades, y n × n n´ umeros d(i, j) ∈ IN para 1 ≤ i, j ≤ n que representan las distancias entre cada dos ciudades (y tales que d(i, j) = d(j, i) y d(i, i) = 0 para todo i, j). ¿Cuánto mide el camino más corto que pasa por todas las ciudades una sola vez? Este problema se llama problema del viajante. Puede resultar sorpendente saber que no se conoce ning´ un algoritmo que resuelva completamente el problema y que sea sustancialmente mejor que la b´ usqueda 75

´ CAPÍTULO 7. COMPLEJIDAD Y CODIFICACION

76

exhaustiva, es decir, probar todos los caminos y quedarse con el más corto. Como para n ciudades hay n! caminos, y n! ≈ nn , este método es bastante lento. El alumno puede intentar encontrar un algoritmo para el problema del viajante que trabaje en tiempo menor que n! para todas las entradas. Vamos a estudiar este problema y muchos otros del mismo tipo para los que no se conocen algoritmos m´ınimamente eficientes. Nos vamos a centrar en problemas decisionales porque son más sencillos de formalizar. Una versión decisional del problema del viajante es la siguiente, que llamaremos TSP: Dados n ∈ IN, d(i, j) ∈ IN para 1 ≤ i, j ≤ n (tales que d(i, j) = d(j, i) y d(i, i) = 0 para todo i, j), y k ∈ IN. ¿Existe un camino que pasa por todas las ciudades una sola vez y que tiene una longitud total menor o igual que k? El pasar de la versión funcional a la versión decisional en este caso puede parecer una gran simplificación pero no lo es tanto si tenemos en cuenta que tampoco se conocen algoritmos eficientes para TSP, y que en realidad la complejidad de TSP es similar a la del problema general, ya que a partir de un algoritmo q que resuelva TSP podemos resolver el problema del viajante usando b´ usqueda dicotómica: Leer N, D PN−1 L SUP:= I=1 D(I,I+1); L INF:=0; Mientras que L INF

7.2.

77

Complejidad en tiempo

Definición 7.1 Dado un algoritmo p y una entrada x, tp (x) es el n´ umero de pasos que tarda p con entrada x. Falta concretar qué consideramos un paso. Un paso es una instrucción de alto nivel, exclu´ıdas las multiplicaciones. Multiplicar dos enteros a y b consideraremos que cuesta log(a) + log(b) pasos. De esta forma podemos asegurar que si y es el resultado de p con entrada x, entonces |y| ≤ |x| · tp (x). En la sección 2.1.2 hemos definido qué es el tama˜ no de una entrada. Vamos a medir la complejidad en tiempo de un programa p en función de la longitud de las entradas, seg´ un la siguiente definición de Tp (m): Definición 7.2 Dado un algoritmo p y m ∈ IN, Tp (m) es el n´ umero de pasos que tarda p con una entrada de tama˜ no m en el caso peor: Tp (m) = máx tp (x) |x|=m

Tanto para tp como para Tp nos interesan las cotas superiores, es decir, Tp (m) ≤ m2 que quiere decir que para cualquier entrada de tama˜ no m, p tarda tiempo 2 como mucho m .

7.3.

C´ omo codificamos las entradas

En esta segunda parte del curso trataremos con datos de diferentes tipos, entre ellos grafos. Vamos a detallar algunas de las codificaciones que utilizaremos y ver cómo podemos acotar el tiempo de un algoritmo en función del tama˜ no de la entrada. Un grafo G = (V, A) es un conjunto de vértices o nodos V y un conjunto de aristas A. Si G es un grafo dirigido, las aristas son pares de vértices (A ⊆ V × V ), es decir, la arista (u, v) es distinta de la (v, u). Si G es un grafo no dirigido, cada arista es un conjunto de dos vértices {u, v}, es decir, las aristas no tienen dirección ( {u, v} = {v, u} ). Para un grafo de n vértices tomaremos siempre como conjunto de vértices V = {1, 2, 3, . . . , n}.


78

Codificaremos los grafos (dirigidos y no dirigidos) de 3 formas distintas: 1. Con la matriz de adyacencia. 2. Con listas de adyacencia. 3. Con la lista de aristas. 1. Dado un grafo de n vértices, la matriz de adyacencia es una matriz M n × n con valores en {0, 1} definida como sigue: para grafos dirigidos (

1 si (i, j) ∈ A 0 si (i, j) 6∈ A

(

1 si {i, j} ∈ A 0 si {i, j} 6∈ A

M (i, j) = para grafos no dirigidos M (i, j) =

La codificación de cada grafo G se realizará sobre {0, 1} y consistirá en la matriz de adyacencia de G escrita por filas, es decir, la codificación de un grafo de n vértices será: M [1, 1]M [1, 2] . . . M [1, n] . . . M [n, n] y por tanto |G| = n2 . Dado un grafo G, el tama˜ no de G con esta primera codificación sólo depende del n´ umero de vértices. Notemos que en el caso de grafos no dirigidos la matriz de adyacencia tiene información redundante, ya que siempre M [i, j] = M [j, i]. 2. Dado un grafo G y un vértice i, la lista de adyacencia de i está formada por los vértices j tales que (i, j) ∈ A (en el caso dirigido) ó {i, j} ∈ A (en el caso no dirigido). Vamos a codificar los grafos utilizando las listas de adyacencia. Los codificamos sobre {0, 1, #, ; }. Para cada vértice inclu´ımos el vértice en binario, su lista de adyacencia con los vértices en binario separados por # y por u ´ltimo ; para separarlo de la siguiente lista, es decir: 1#b11 #b21 # . . . #bx1 1 ; 2#b12 # . . . #bxnn ;


79

donde b1i , . . . , bxi i es la lista de adyacencia de vértice i. El tama˜ no de G depende ahora del tama˜ no de cada lista de adyacencia y del n´ umero de vértices. Si tenemos un grafo G con n vértices y k aristas, podemos acotar superiormente |G| con |G| ≤ n(log(n) + 2 + k(log(n) + 2)) (para cada vértice aparece como máximo su n´ umero (≤ log(n) + 1 bits) y hasta k elementos en su lista de adyacencia, cada uno un máximo de log(n) + 2 s´ımbolos). Podemos acotar inferiormente |G| con |G| ≥ 2n + 2k (para cada vértice aparece al menos un bit con su n´ umero y el separador ; y por cada arista aparece un elemento de una lista de adyacencia lo cual es al menos un bit con un n´ umero y el separador #). 3. Podemos codificar un grafo dirigido G con las aristas (a1 , b1 ) (a2 , b2 ) . . . (ak , bk ) (o un grafo no dirigido G con las aristas {a1 , b1 }{a2 , b2 } . . . {ak , bk }) sobre {0, 1, #, (, )} simplemente dando el n´ umero de vértices en binario, seguido de la lista de aristas, escribiendo los n´ umeros de los vértices en binario: n(a1 #b1 )(a2 #b2 ) . . . (ak #bk ) De esta forma |G| ≤ log(n) + 1 + k(2 log(n) + 5) y |G| ≥ log(n) + 1 + 5k. Ejemplo 7.3 Sea G el siguiente grafo no dirigido:


80

Su codificación seg´ un 1. será 0101100000001000 seg´ un 2. 1#10#100; 10#1; 11; 100#1; y seg´ un 3. 100(1#10)(1#100)

7.4.

Transformaci´ on de cotas de tiempo

Hemos visto que la codificación concreta que se elige influye de forma importante sobre el tama˜ no de las entradas. Veamos ahora cómo podemos pasar de una cota dada a un algoritmo en función de una parte de la entrada a una en función del tama˜ no de la entrada. Sean p y q dos algoritmos que resuelven un problema con entrada un grafo. Dado un grafo G, llamamos n al n´ umero de vértices y k al n´ umero de aristas. Supongamos que tenemos las siguientes dos cotas para la complejidad en tiempo de p y q: tp (G) ≤ 2n3 + 6n tq (G) ≤ 3k 2 Veamos cómo transformar las cotas anteriores en otras cotas que dependen sólo del tama˜ no de la entrada. Para ello necesitamos desigualdades de la forma n ≤ f1 (|G|) ó k ≤ f2 (|G|) para combinarlas con las dos desigualdades anteriores. 1. Primera codificación. Sabemos que |G| ≥ n2 , luego n ≤ tanto Tp (m)

q

|G| y por

= máx|G|=m tp (G) ≤ máx|G|=m 2n3 + 6n ≤ ≤ máx|G|=m 2|G|3/2 + 6|G|1/2 ≤ 2m3/2 + 6m1/2

Para el caso de q, cuyo tiempo tenemos acotado en función del n´ umero de aristas, sabemos que k ≤ n2 , luego |G| ≥ n2 ≥ k, por tanto Tq (m) = máx tq (G) ≤ máx 3k 2 ≤ máx 3|G|2 = 3m2 |G|=m

|G|=m

|G|=m


81

2. Segunda codificación. Sabemos que |G| ≥ 2n + 2k luego |G| ≥ k y |G| ≥ n. Por tanto Tp (m) = máx tp (G) ≤ máx 2n3 +6n ≤ máx 2|G|3 +6|G| ≤ 2m3 +6m |G|=m

|G|=m

|G|=m

De la misma forma Tq (m) ≤ 3m2 3. Tercera codificación. Sabemos que |G| ≥ log(n) + 1 + 5k ≥ log(n). Por tanto n ≤ 2|G| . No podemos dar una cota inferior de |G| en función de n mucho mejor, porque por ejemplo en el caso de un grafo de n vértices y ninguna arista, |G| = log(n) + 1 y n = 2|G|−1 . Por tanto máx|G|=m tp (G) ≤ máx|G|=m 2n3 + 6n

Tp (m) =

≤ máx|G|=m 23|G|+1 + 6 · 2|G| ≤ 23m+1 + 6 · 2m Para el caso de q, sabemos que |G| ≥ k, luego Tq (m) ≤ 3m2 Como vemos, para pasar de una cota superior de tp (x) que depende de una parte de la entrada z a una cota superior de Tp (m) en función del tama˜ no de la entrada |x| el método es: Hacer una cota de la forma |x| ≥ g(z). Pasar a f (|x|) ≥ z. Acotar Tp (m) usando la cota de tp (x) que depende de z y el hecho de que z ≤ f (|x|).

Cap´ıtulo 8

Tiempo polin´ omico versus tiempo exponencial Referencia: Cap´ıtulos 1 y 2 de [GJ78]. En este cap´ıtulo estudiaremos P y EXP, dos clases o conjuntos de problemas decisionales. La clase EXP contiene casi todos los problemas que intentaréis resolver con un algoritmo. P es una parte de EXP formada por los problemas que se pueden resolver eficientemente o resolubles en la práctica.

8.1.

Definiciones

Definición 8.1 Dada una función f : IN → IN, llamamos O(f ) al conjunto O(f ) = {h : IN → IN | ∃c > 0 tal que h(m) ≤ c · f (m) ∀m} (es decir, O(f ) es el conjunto de funciones acotadas por c·f , para alguna constante c). Vamos a clasificar los problemas decisionales seg´ un el tiempo que se tarda en resolverlos en función del tama˜ no de la entrada y en el caso peor, es decir, seg´ un Tp . Definición 8.2 Dada una función f : IN → IN llamamos DTIME(f (m)) a la clase de problemas: 82

´ CAPÍTULO 8. TIEMPO POLINOMICO VERSUS TIEMPO ...

DTIME(f (m)) = { Π |

83

Π es un problema decisional y existe un algoritmo q que lo resuelve y cumple Tq ∈ O(f ) }.

Es decir, DTIME(f (m)) es el conjunto de problemas resolubles en tiempo menor o igual que c · f , para alguna constante c. Es importante notar que f es una cota superior, un problema que está en DTIME(f (m)) puede tener un programa que lo resuelva en tiempo mucho menor que f (m). Definición 8.3 P es el conjunto de problemas resolubles en tiempo (menor o igual que) polinómico, es decir DTIME(mk )

[

P=

k∈IN

EXP es el conjunto de problemas resolubles en tiempo (menor o igual que) exponencial, es decir EXP =

[

k

DTIME(2m )

k∈IN k

k

Insistimos en que en DTIME(2m ), 2m es cota superior, no tiene pork que ser igualdad, el tiempo de un problema en DTIME(2m ) puede ser k mucho menor que 2m . Teorema 8.4 P ⊆ EXP Dem. Para cualquier k, sabemos que mk ∈ O(2m ) (ya que l´ımm mk /2m = 0), luego DTIME(mk ) ⊆ DTIME(2m ) y por tanto P ⊆ EXP. Se sabe que P 6= EXP (luego P ⊂ EXP). Esto quiere decir que hay más problemas en EXP que los de P, es decir, hay alg´ un problema que se puede resolver en tiempo acotado por una exponencial pero no por un polinomio.


8.2.

84

Problemas resolubles en la pr´ actica

P es el conjunto de problemas considerados resolubles en la práctica. Esto quiere decir que si un problema Π no está en P se considera no resoluble de forma eficiente. Las razones de P se considere el l´ımite de lo resoluble de forma eficiente son de ´ındole práctico y se resumen en: 1. La mayor´ıa de los algoritmos q que se implementan cumplen Tq (m) ∈ O(mk ) para alg´ un k. 2. Los problemas naturales que se sabe que están en P tienen algoritmos “rápidos” (que cumplen Tq (m) ≤ c · mk para k ≤ 3 y c peque˜ na), luego se pueden resolver en tiempo polinómico pero para polinomios muy peque˜ nos. 3. Los problemas naturales para los que no se conocen algoritmos polinómicos, tampoco tienen algoritmos conocidos con tiempo muy por debajo de una exponencial 2cm , es decir, no se conocen algoritmos para problemas interesantes con tiempos intermedios como 2 mlog(m) , mlog(m) , etc. Por tanto en la práctica se trata de comparar algoritmos que tardan tiempo mk con algoritmos que tardan tiempo al menos 2m . Basta examinar las tablas siguientes para ver que los algoritmos que tardan tiempo 2m ó más son in´ utiles en la práctica. Considerando la velocidad de un pentium 4 (cada instrucción tarda alrededor de 1,5 ×10−9 segundos, suponiendo una velocidad de 2,4 GHz y 4 ciclos por instrucción) veamos en la siguiente tabla cuánto valen las funciones de tiempo m, m2 , m3 , m5 , 2m y 3m para distintos valores de m.


m = 10 m 1,5×10−8 seg. 2 m 1,5×10−7 seg. 3 m 1,5×10−6 seg. 5 m 1,5×10−4 seg. 2m 1,5×10−6 seg. 3m 8,8×10−5 seg.

20 3×10−8 seg. 6×10−7 seg. 1,2×10−5 seg. 0,0048 seg. 0,0015 seg. 5,2 seg.

A continuación vemos el hora: tiempo computador de hoy m N1 = 24 · 1011 2 m N2 = 1550000 3 m N3 = 13200 m5 N4 = 300 m 2 N5 = 41, 1 m 3 N6 = 25, 9

30 4,5×10−8 seg. 1,35×10−6 seg. 4×10−5 seg. 0,036 seg. 1,611 seg. 3 d´ıas

40 6×10−8 seg. 2,4×10−6 seg. 9,6×10−5 seg. 0,15 seg. 27,6 minutos 5,8 siglos

85

50 7,5×10−8 seg. 3,75×10−6 seg. 1,9×10−4 seg. 0,47 seg. 19 d´ıas 3×105 siglos

60 9×10−8 seg. 5,4×10−6 seg. 3,2×10−4 seg. 1,17 seg. 59,4 a˜ nos 2×1010 siglos

mayor tama˜ no de entrada resoluble en una 100 veces más rápido 100N1 10N2 4,64N3 2,5N4 N5 +6,64 N6 +4,19

1000 veces más rápido 1000N1 31,6N2 10N3 3,98N4 N5 +9,97 N6 +6,29

Esta tabla presenta el efecto de la mejora tecnológica el varios algoritmos de tiempo polinómico y exponencial. En los siguientes cap´ıtulos nos ocuparemos de muchos problemas que es importante resolver eficientemente, ya que aparecen en todo tipo de aplicaciones, pero para los cuales no se conocen algoritmos eficientes, es decir, no se sabe que estén en P. Terminamos se˜ nalando que existen algunos (pocos) problemas para los que el mejor algoritmo conocido tarda tiempo exponencial en el caso peor (Tp (m) ≈ 2m ) pero que funcionan bien en la práctica, por ejemplo el problema de la mochila. Esto es debido a que la definición de Tp (m) es en caso peor, pero para las entradas más frecuentes tp (x) se mantiene bajo y son entradas menos usadas las que hacen Tp (m) exponencial. Este comportamiento anómalo se da para muy pocos problemas.


8.3.

86

Tesis extendida de Turing-Church

Hemos estudiado distintos modelos de cálculo, que son equivalentes respecto a la definición de función calculable (y por tanto conjunto decidible, que corresponde a problema decisional resoluble). Vamos a comparar ahora estos modelos respecto a la definición de las clases P y EXP. Tomando el modelo de las máquinas de Turing, cada máquina calcula una función a base de acciones elementales o transiciones, cada una de ellas consistente en cambiar de estado, escribir un s´ımbolo y moverse una casilla. Llamamos paso a cada una de estas transiciones. Definición 8.5 Dada una máquina de Turing M defino tM y TM como: tM (x) =

N´ umero de pasos de M con entrada x desde que empieza hasta que se para. TM (m) = máx tM (x). |x|=m

Ahora podemos definir clases de problemas decisionales clasificándolos a partir de TM : Definición 8.6 Dada una función f : IN → IN, llamamos DTIME1 (f (m)) a la clase: DTIME1 (f (m)) = { Π |

Π es un problema decisional y existe una máquina M que lo resuelve y cumple TM ∈ O(f ) }.

El siguiente resultado técnico relaciona las clases DTIME y DTIME1 : Lema 8.7 Dada una funci´ on f : IN → IN que sea total, creciente y k recursiva (por ejemplo f (m) = mk y f (m) = 2m ) DTIME1 (f (m)) ⊆ DTIME(f 3 (m)) DTIME(f (m)) ⊆ DTIME1 (f 3 (m)) Omitimos la demostración, que requiere manejo avanzado de las máquinas de Turing. Por tanto podemos definir P y EXP utilizando máquinas de Turing:


87

Corolario 8.8 P =

[

DTIME1 (mk )

k∈IN

EXP =

[

k

DTIME1 (2m )

k∈IN

Dem. Por el lema anterior, para cada k ∈ IN, DTIME1 (mk ) ⊆ DTIME(m3k ) ⊆ P luego [

DTIME1 (mk ) ⊆ P

k∈IN

También para cada k ∈ IN, DTIME(mk ) ⊆ DTIME1 (m3k ) luego P=

[ k∈IN

DTIME(mk ) ⊆

[

DTIME1 (mk )

k∈IN

En general, para cada uno de los modelos conocidos con una definición natural de paso, P y EXP corresponden a tiempo polinómico y exponencial respectivamente. Por ejemplo, en el λ-cálculo, un paso es una aplicación de la regla de reescritura. Esta situación ha motivado la siguiente tesis o conjetura: Tesis extendida de Turing-Church: Para cualquier modelo razonable (y secuencial) de cálculo, P y EXP corresponden a n´ umero de pasos polinómico y exponencial respectivamente. La conjetura anterior está siendo replanteada a la luz de los recientes estudios sobre el computador cuántico. Este modelo, formulado en 1982 por Deutsch, Lloyd y Feynman es de naturaleza muy distinta a los otros modelos secuenciales. En 1994, Nishino resolvió con este modelo en tiempo polinómico problemas para los que no se conocen algoritmos polinómicos. También Shor


88

en el 94 provó que es posible factorizar n´ umeros en tiempo medio polinómico con un computador cuántico, lo cual hasta el momento no se ha conseguido con los computadores tradicionales. Si embargo, a pesar de los m´ ultiples intentos de varios grupos de investigadores, no se ha constru´ıdo todav´ıa un computador cuántico, y todav´ıa no está claro si será viable construirlo en el futuro. EJERCICIOS 8.1. Demostrar que los siguientes problemas están en la clase P. 1. Mochila-fácil: Datos: n, p1 , . . . , pn , k, C ∈ IN Salida: ¿Existe A ⊆ {1, . . . , n} con #A = k y Σi∈A pi ≤ C ? Codificación de las entradas: sobre el alfabeto Σ = {0, 1, ,}, los n+3 n´ umeros naturales que componen una entrada se escriben en binario y se separan por comas. Pista: Ordenar p1 , . . . , pn . 2. 2-color: Datos: G = (V, A) grafo dirigido. Salida: ¿Pueden etiquetarse los vértices de G con dos colores de manera que los dos vértices de cada arista tengan colores diferentes? Codificación de las entradas: sobre el alfabeto Σ = {0, 1, ,}, si u ∈ {0, 1}∗ es el n´ umero de vértices escrito en binario y ∗ v ∈ {0, 1} es la matriz de adyacencia de G escrita por filas, entonces la codificación de la entrada G es la palabra u, v. Pista: Es equivalente a dividir V en dos conjuntos V1 y V2 de manera que no haya ninguna arista de un vértice de V1 a otro de V1 , ni de uno de V2 a otro de V2 . 3. Path-bet-two-vertices: Datos: G = (V, A) grafo dirigido, u, v ∈ V Salida: ¿Existe un camino de u a v?


89

Codificación de las entradas: sobre el alfabeto Σ = {0, 1, ,}, si a ∈ {0, 1}∗ es el n´ umero de vértices escrito en binario, b ∈ {0, 1}∗ es la matriz de adyacencia de G escrita por filas, y x, y son u, v en binario, entonces la codificación de la entrada G, u, v es la palabra a, b, x, y. Pista: Calcular el conjunto de los vértices que están a distancia menor o igual que n de u de forma incremental. 4. Shortest-Path-bet-two-vertices: Datos: G = (V, A) grafo dirigido, u, v ∈ V , k ∈ IN Salida: ¿Existe un camino de u a v de longitud menor o igual a k? Codificación de las entradas: sobre el alfabeto Σ = {0, 1, ,}, si a ∈ {0, 1}∗ es el n´ umero de vértices escrito en binario, b ∈ ∗ {0, 1} es la matriz de adyacencia de G escrita por filas, x, y son u, v en binario, y z es k en binario, entonces la codificación de la entrada G, u, v, k es la palabra a, b, x, y, z. 5. Modulo: Datos: a, b, c ∈ IN Salida: ¿Existe un x ∈ IN tal que x < c y x ≡ a (mód b)? Codificación de las entradas: sobre el alfabeto Σ = {0, 1, ,}, los 3 n´ umeros naturales que componen una entrada se escriben en binario y se separan por comas.

Cap´ıtulo 9

Estudio de algunos problemas importantes; la clase NP Referencia: Cap´ıtulos 2.6 y 3.1 de [GJ78]. En este cap´ıtulo estudiaremos tres problemas importantes: SAT, MOCHILA y CLIQUE, y definiremos la clase NP a la que pertenencen esos tres problemas.

9.1.

SAT

Sea X = {x1 , . . . , xn } un conjunto de variables booleanas. Definición 9.1 Un literal sobre X es una variable x ∈ X o su negación ¬x. Definición 9.2 Una cláusula sobre X es una disyunción de literales. Ejemplos 9.3 Sea n = 8. Son cláusulas sobre X: x2 ∨ ¬x3 ∨ x8 ¬x2 Definición 9.4 Una fórmula CNF sobre X es una conjunción de cláusulas. Ejemplos 9.5 Sea n = 15. Son fórmulas CNF las siguientes: 90

CAPÍTULO 9. ESTUDIO DE ALGUNOS PROBLEMAS ...

91

(x7 ∨ x15 ) ∧ (x2 ∨ ¬x3 ∨ x8 ) (¬x2 ) ∧ (x4 ∨ ¬x2 ) Definición 9.6 Una asignación de verdad de X es una función α : X → {T, F }, es decir, una función que asigna a cada variable el valor T (cierto) o el F (falso). Definición 9.7 Dada una fórmula L y una asignación de verdad α, α satisface L si al sustituir cada variable x por α(x) en L y operar seg´ un la definición habitual de los operadores booleanos ¬, ∨, ∧, el resultado es T . Ejemplos 9.8 α(x1 ) = T, α(x2 ) = F, α(x3 ) = T, α(x4 ) = T satisface la fórmula (¬x2 ) ∧ (x4 ∨ ¬x2 ). Ya podemos definir el problema SAT. Restringiremos las entradas a fórmulas en las que aparecen todas las variables de X. Datos: Un conjunto de variables X y una fórmula CNF sobre X, L (que cumplen que todas las variables de X aparecen al menos una vez en L). Salida: ¿Existe una asignación de verdad que satisface L? Es decir, el problema se trata de saber si una cierta fórmula CNF se puede hacer cierta o si por el contrario es falsa para cualquier asignación. Por ejemplo, cualquiera de los ejemplos anteriores son fórmulas para las que existen asignaciones que las satisfacen. No existe ninguna asignación que satisfaga la fórmula (x2 ∨ x1 ) ∧ (¬x2 ∨ x1 ) ∧ (¬x2 ∨ ¬x1 ) ∧ (x2 ∨ ¬x1 ) ∧ (x2 ∨ ¬x2 ). Tenemos que especificar la codificación de las entradas del problema anterior. Vamos a utilizar el alfabeto Σ = {0, 1, ¬, (, ), #, ∨, ∧} y codificar una entrada X, L como el n´ umero de variables n en binario, seguido de la fórmula escribiendo los n´ umeros de variable en binario y los s´ımbolos de las operaciones lógicas necesarios. Por ejemplo, X = {x1 , x2 , x3 }, L = (x2 ∨ ¬x1 ) ∧ x3 se codifica como 11#(10 ∨ ¬1) ∧ 11 Vamos a relacionar el tama˜ no de una entrada X, L con el n´ umero de variables n y el n´ umero de cláusulas de la fórmula k:


92

Como hemos restringido a las fórmulas en las que aparecen todas las variables de X, y para cada una de las variables que aparece en L hay que escribir al menos un bit con el n´ umero de variable, |X, L| ≥ n. Para cada cláusula hay que escribir al menos un s´ımbolo, luego |X, L| ≥ k. El algoritmo de b´ usqueda exhaustiva, es decir, el que con entrada X, L eval´ ua la fórmula L con cada una de las 2n asignaciones posibles, tarda tiempo tp (X, L) ≤ 2n ·(“tiempo de evaluar00 ), veremos más adelante que podemos evaluar L con una determinada asignación en tiempo menor o igual que una constante c por kn. Como |X, L| ≥ n, |X, L| ≥ k, 2 2 Tp (m) ≤ 2m (cm2 ) ∈ O(2m ). Por tanto SAT ∈ DTIME(2m ) y SAT ∈ EXP. Pero ya hemos hablado de la inutilidad práctica de las cotas de tiempo exponenciales. Lo que ocurre es que no se conoce ning´ un algortimo que resuelva todas las entradas de SAT y tarde tiempo (en caso peor) sustancialmente menor que la b´ usqueda exhaustiva. Estudiamos a continuación el problema de evaluación de fórmulas booleanas (EVAL), mucho más simple de resolver que SAT: Datos: Un conjunto de variables X, una fórmula CNF sobre X, L y una asignación de verdad α (que cumplen que todas las variables de X aparecen al menos una vez en L). Salida: ¿α satisface L? La codificación de las entradas de EVAL, sobre el alfabeto Σ = {0, 1, ¬, (, ), #, ∨, ∧}, se basa en la codificación de las entradas de SAT, pero tenemos que especificar la codificación de las asignaciones de verdad. Una asignación α sobre n variables la codificaremos con n bits w1 . . . wn de forma que wi = 1 si α(xi ) = T y wi = 0 si α(xi ) = F . La codificación de una entrada X, L, α será la codificación de X, L como entrada de SAT, seguida de #, seguida de la codificación de α descrita anteriormente, luego |X, L, α| = |X, L| + n + 1. Un simple algoritmo para EVAL es el que primero sustituye cada literal de L por su valor correspondiente seg´ un α y después va simplificando los operadores booleanos:


93

Leer X, L, α /* X= {x1 , . . . , xn }, L= c1 ∧ c2 ∧ . . . ∧ ck , con ci clausula para 1 ≤ i ≤ k */ Para I=1 hasta k hacer Para cada H literal de cI hacer Si H=x sustituir H por α(x) else Si H=¬x sustituir H por ¬α(x) /* Sustituyo por T si α(x)=F, por F si α(x)=T */ Fpara; Fpara; RESULTADO:=TRUE; I:=1; Mientras que (I<= k) AND RESULTADO hacer ESTACLAUSULA:=FALSE; Mientras que (NOT ESTACLAUSULA) AND (ci 6= ∅) hacer Quitar CTE la siguiente constante de ci ; Si CTE=T entonces ESTACLAUSULA:=TRUE; Fmq; RESULTADO:=RESULTADO AND ESTACLAUSULA; I:=I+1; Si RESULTADO entonces Devuelve SI else Devuelve NO. Si p es el algoritmo anterior, como el n´ umero de literales por cláusula es como máximo 2n, tp (X, L, α) ≤ k · 2n + 2 + k(3 + 4n) + 1 ≤ 12kn Como |X, L, α| ≥ |X, L|, entonces |X, L, α| ≥ n y |X, L, α| ≥ k. Por tanto Tp (m) ≤ 12m2 , EVAL ∈ DTIME(m2 ) ⊆ P. La diferencia de tama˜ no entre las entradas de SAT y las de EVAL no es muy grande, ya que |α| = n ≤ |X, L|. Observemos que X, L tiene solución S´ı para SAT ⇔ ∃α, |α| ≤ |X, L| X, L, α tiene solución S´ı para EVAL Como conjuntos, SAT = {X, L | ∃α, |α| ≤ |X, L| X, L, α ∈ EVAL}.


94

Esto se puede expresar informalmente como “podemos COMPROBAR SAT en tiempo polinómico”, ya que EVAL es el problema de comprobar que un determinado α hace que X, L tenga solución S´ı para SAT.

9.2.

MOCHILA

Sea MOCHILA el siguiente problema: Datos: n ∈ IN el n´ umero de objetos, p1 , . . . , pn ∈ IN los pesos de los objetos, P ∈ IN el peso máximo que ite la mochila, y d ∈ IN el hueco máximo permitido (d ≤ P ). Salida: ¿Existe un conjunto de objetos A ⊆ {1, . . . , n} que cumpla: P −d≤

X

pi ≤ P ?

i∈A

Es decir, ¿existe una forma de llenar la mochila pesando como m´ınimo d menos que el máximo permitido? Codificamos la entrada con el alfabeto Σ = {0, 1, #}, cada natural en binario y separados por #: n#p1 # . . . #pn #P #d Vamos a relacionar el tama˜ no de una entrada n, p1 , . . . , pn , P, d con el n´ umero de objetos n y con M = máx{p1 , . . . , pn , P }: Como hay que escribir n + 3 n´ umeros en binario, |n, p1 , . . . , pn , P, d| ≥ n. Como hay que escribir al menos una vez en binario el n´ umero M, |n, p1 , . . . , pn , P, d| ≥ log(M ). El algoritmo de b´ usqueda exhaustiva, es decir, el que con entrada n, p1 , . . . , pn , P, d P calcula el valor de i∈A pi para cada uno de los 2n subconjuntos de {1, . . . , n}, tarda tiempo tp (n, p1 , . . . , pn , P, d) ≤ 2n · n, ya que podemos calcular una suma de como máximo n naturales en tiempo menor o igual 2 que n. Como |n, p1 , . . . , pn , P, d| ≥ n, Tp (m) ≤ 2m · m ∈ O(2m ). Por 2 tanto MOCHILA ∈ DTIME(2m ) ⊆ EXP.


95

Para MOCHILA tampoco se conoce ning´ un algortimo que resuelva todas las entradas y tarde tiempo (en caso peor) sustancialmente menor que la b´ usqueda exhaustiva. Estudiamos a continuación una versión muy simplificada de MOCHILA, que llamamos compMOCHILA: Datos: n ∈ IN, p1 , . . . , pn ∈ IN, P ∈ IN, d ∈ IN (d ≤ P ) y A un subconjunto de {1, . . . , n}. Salida: ¿Se cumple: P −d≤

X

pi ≤ P ?

i∈A

La codificación de las entradas de compMOCHILA, sobre el alfabeto Σ = {0, 1, #}, se basa en la codificación de las entradas de MOCHILA, pero tenemos que especificar la codificación de los subconjuntos de {1, . . . , n}. Un subconjunto de {1, . . . , n} lo codificaremos con n bits w1 . . . wn de forma que wi = 1 si i ∈ A y wi = 0 si i 6∈ A. La codificación de una entrada n, . . . , d, A será la codificación de n, . . . , d como entrada de MOCHILA, seguida de #, seguida de la codificación de A descrita anteriormente, luego |n, . . . , d, A| = = |n, . . . , d| + n + 1. Un algoritmo para compMOCHILA es un u ńico bucle que para una P entrada n, p1 , . . . , pn , P, d, A calcula i∈A pi . Si q es este algoritmo, tq (n, p1 , . . . , pn , P, d, A) ≤ n Como |n, p1 , . . . , pn , P, d, A| ≥ |n, p1 , . . . , pn , P, d| ≥ n, Tq (m) ≤ m, compMOCHILA ∈ DTIME(m) ⊆ P. La diferencia de tama˜ no entre las entradas de MOCHILA y las de compMOCHILA no es muy grande, ya que |A| = = n ≤ |n, . . . , d|. Observemos que

n, p1 , . . . , pn , P, d tiene solución S´ı para MOCHILA ⇔ ∃A, |A| ≤ |n, p1 , . . . , pn , P, d| n, p1 , . . . , pn , P, d, A tiene solución S´ı para compMOCHILA Esto se puede expresar informalmente como “podemos COMPROBAR MOCHILA en tiempo polinómico”.


96

También podemos escribir MOCHILA como:

MOCHILA = {n, p1 , . . . , pn , P, d | ∃A, |A| ≤ |n, p1 , . . . , pn , P, d| n, p1 , . . . , pn , P, d, A ∈ compM

9.3.

CLIQUE

Sea G = (V, A) un grafo no dirigido. Definición 9.9 Un clique de G es un conjunto de vértices U ⊆ V que forma un subgrafo completo, es decir, que cumple ∀u, v ∈ U, u 6= v {u, v} ∈ A Esto es, los vértices de U están unidos por todas las aristas posibles. El problema que tratamos aqu´ı es la b´ usqueda de cliques lo más grandes posibles. En versión decisional aparece el problema que sigue. Sea CLIQUE el siguiente problema: Datos: G = (V, A) un grafo no dirigido con n vértices, k ∈ IN con k ≤ n. Salida: ¿Existe un clique de G con k vértices? Codificamos la entrada con el alfabeto Σ = {0, 1, #}, utilizando la codificación del grafo con matriz de adyacencia, después # seguida de la codificación de k en binario. Vamos a relacionar el tama˜ no de una entrada G, k con el n´ umero de 2 2 vértices n, sabemos que |G| = n , luego |G, k| ≥ n . El algoritmo de b´ usqueda exhaustiva, es decir, el que con entrada G, k prueba cada subconjunto de k vértices de G como posible clique, tiene n que probar k subconjuntos y para cada uno de ellos chequear la existencia de k(k −1)/2 aristas. Por tanto tarda tiempo tp (G, k) ≤ 1/2

n k

·k 2 ≤

2n ·n2 . Como |G, k| ≥ n2 Tp (m) ≤ 2m ·m ∈ O(2m ). Por tanto CLIQUE ∈ DTIME(2m ) ⊆ EXP. Para CLIQUE tampoco se conoce ning´ un algoritmo que resuelva todas las entradas y tarde tiempo (en caso peor) sustancialmente menor que la b´ usqueda exhaustiva.


97

Estudiamos a continuación una versión comprobación que llamamos compCLIQUE: Datos: G = (V, A) grafo no dirigido, k ∈ IN, U subconjunto de V de k elementos. Salida: ¿Es U un clique de G ? La codificación de las entradas de compCLIQUE, sobre el alfabeto Σ = {0, 1, #}, se basa en la codificación de las entradas de CLIQUE, pero tenemos que especificar la codificación de los subconjuntos de k elementos de {1, . . . , n}. Un subconjunto de k elementos de {1, . . . , n} lo codificaremos listando sus elementos en binario, por orden y separados por #. Por ejemplo U = {2, 6, 3} lo codificaremos como 10, 11, 110. La codificación de una entrada G, k, U será la codificación de G, k como entrada de CLIQUE, seguida de #, seguida de la codificación de U descrita anteriormente, luego |G, k, U | ≥ |G, k| ≥ n2 . Un algoritmo para compCLIQUE es un u ńico bucle que para una entrada G, k, U comprueba si todas las parejas u, v con u, v ∈ U son aristas de G. Si q es el algoritmo anterior, tq (G, k, U ) ≤ k 2 ≤ n2 Como |G, k, U | ≥ n2 , Tq (m) ≤ m, compCLIQUE ∈ DTIME(m) ⊆ P. La diferencia de tama˜ no entre las entradas de CLIQUE y las de compCLIQUE no es muy grande, ya que |U | ≤ k · (log(n) + 2) ≤ n · (log(n) + 2) ≤ 3 · n2 , |G, k| ≥ n2 , luego |U | ≤ 3 · |G, k|. Observemos que G, k tiene solución S´ı para CLIQUE ⇔ ∃U, |U | ≤ 3 · |G, k| G, k, U tiene solución S´ı para compCLIQUE Esto se puede expresar informalmente como “podemos COMPROBAR CLIQUE en tiempo polinómico”. CLIQUE = {G, k | ∃U, |U | ≤ 3 · |G, k| G, k, U ∈ compCLIQUE}.


9.4.

98

La clase NP

Hemos visto que los tres problemas anteriores, SAT, MOCHILA y CLIQUE, tienen una propiedad en com´ un, son comprobables en tiempo polinómico. Existen muchos problemas que cumplen esta propiedad, son los que forman la clase NP. Definición 9.10 Dado un problema decisional Π, Π es comprobable en tiempo polinómico si existe un problema Λ ∈ P y una constante c que cumplen, para cualquier x entrada de Π: x tiene solución S´ı para Π ⇔ ∃y, |y| ∈ O(|x| ), con x, y una entrada con solución S´ı para Λ. c

Es decir, como conjunto, Π = {x | ∃y, |y| ∈ O(|x|c ) x, y ∈ Λ}. Definición 9.11 NP es el conjunto de problemas comprobables en tiempo polinómico. Para demostrar que un problema está en NP tenemos que encontrar un problema Λ (versión comprobación de Π) y dos constantes c, c0 que cumplan: 1. Λ ∈ P. 2. Una entrada x, y de Λ, con x entrada de Π, cumple |y| ≤ c0 · |x|c . 3. x tiene solución S´ı para Π ⇔ ∃y tal que x, y tiene solución S´ı para Λ. Ejemplos 9.12 Los siguientes problemas están en NP: SAT, ya que EVAL ∈ P, las entradas X, L, α de EVAL cumplen |α| ≤ |X, L| y por definición de EVAL se cumple 3.


99

MOCHILA, ya que compMOCHILA ∈ P, las entradas n, p1 , . . . , pn , d, A de compMOCHILA cumplen |A| ≤ |n, p1 , . . . , pn , d| y por definición de compMOCHILA se cumple 3. CLIQUE, ya que compCLIQUE ∈ P, las entradas G, k, U de compCLIQUE cumplen |U | ≤ 3|G, k| y por definición de compCLIQUE se cumple 3. Resumiendo, los problemas de NP son aquellos que tienen una versión comprobación que está en P, y de manera que las entradas de la versión comprobación no tengan tama˜ no mucho mayor que el problema original. Veamos dos propiedades importantes de NP. Propiedad 9.13 P ⊆ NP. Dem. Sea Π ∈ P. Considero una versión comprobación trivial Λ: Datos: x entrada de Π, w ∈ {0, 1}∗ con |w| = 1. Salida: ¿x tiene respuesta S´ı para Π ? Si Σ es el alfabeto para codificar las entradas de Π, codifico las entradas de Λ sobre Σ ∪ {0, 1, k}. Para codificar x, w a˜ nado a la codicación de x kw, luego |w| ≤ |x|. Como |x, w| ≥ |x|, un algoritmo q para Λ que ignore w y utilice p un algoritmo para Π tarda tiempo Tq (m) ≤ Tp (m) luego Λ ∈ P. Es trivial que x tiene solución S´ı para Π ⇔ ∃w, |w| ≤ |x| tal que x, w tiene solución S´ı para Λ. Propiedad 9.14 NP ⊆ EXP. Dem. Sea Π ∈ NP. Sea Λ ∈ P el que cumple la definición 9.10. Sean c, c0 las constantes tales que si x, y es entrada de Λ, x entrada de Π, entonces |y| ≤ c0 · |x|c . Sea p un algoritmo en tiempo polinómico para Λ. Sean k, k 0 constantes tales que Tp (m) ≤ k 0 · mk .


100

Podemos construir un algoritmo q para Π que con entrada x prueba todas las posibles y con |y| ≤ c0 · |x|c para ver si x, y da solución s´ı para Λ: Leer X Para cada Y con |Y| ≤ c0 |X|c hacer RESPUESTA:= p(X,Y); Si RESPUESTA = SI entonces Devuelve SI; Fin; Fpara; Devuelve NO. Sea a el n´ umero de s´ımbolos del alfabeto que codifica las entradas de Λ. El n´ umero de y que cumplen |y| ≤ c0 |x|c es 0

c

ac |x| +1 − 1 a−1 Luego tq (x) ≤ ≤ 0

c

Como ac |x| = 2c

0

ac

0 |x|c +1

−1

a−1 0

c

ac |x| a−1

· Tp (c0 |x|c )

· k 0 c0k · (|x|c )k

log(a)|x|c

tq (x) ≤ k 0 c0k /(a − 1) · 2c c+1

Luego Tq (m) ∈ O(2m

0

log(a)|x|c

· (|x|c )k ∈ O(2|x|

c+1

)

) y Π ∈ EXP.

As´ı pues sabemos que P ⊆ NP ⊆ EXP. Estas son todas las relaciones conocidas entre NP y las clases P y EXP. Se sospecha que P 6= NP, es decir, que existan problemas comprobables en tiempo polinómico pero no resolubles en tiempo polinómico, pero no existe ninguna prueba de ello. Lo que tenemos son muchos problemas en NP, los llamados NP-completos, que no se saben resolver en tiempo polinómico. Los estudiaremos en los siguientes cap´ıtulos. EJERCICIOS 9.1. Demostrar que los siguientes problemas están en la clase NP.


101

1. TSP. 2. Compuesto: Datos: n ∈ IN Salida: ¿Existen x, y ∈ IN tal que x > 1, y > 1 y n = x · y? Codificación de las entradas: sobre el alfabeto Σ = {0, 1}, en binario. 3. Linear Divisibility: Datos: a, c ∈ IN Salida: ¿Existe un x ∈ IN tal que ax + 1 divide a c? Codificación de las entradas: sobre el alfabeto Σ = {0, 1, ,}, los 2 n´ umeros naturales que componen una entrada se escriben en binario y se separan por comas. 4. Hitting-Set: Datos: n ∈ IN, A1 , . . . , Al subconjuntos de {1, . . . , n}, k ∈ IN Salida: ¿Existe A ⊆ {1, . . . , n} con #A ≤ k y para todo i ≤ l, Ai ∩ A 6= ∅? Codificación de las entradas: sobre el alfabeto Σ = {0, 1, ,}, n y k se escriben en binario, cada subconjunto de {1, . . . , n} se escribe con n bits (utilizando la secuencia caracter´ıstica) y los l + 2 datos se separan por comas. 5. Multiprocessor Scheduling Datos: n ∈ IN el numero de tareas, l1 , . . . , ln el tiempo de cada tarea, M ∈ IN el n´ umero de procesadores C ∈ IN el tiempo máximo permitido Salida: ¿Podemos repartir la n tareas entre los M procesadores de manera que cada procesador tarde un tiempo menor o igual a C?, es decir, ¿Existen A1 , . . . , AM subconjuntos de {1, . . . , n} tales que A1 ∪ A2 . . . ∪ AM = {1, . . . , n} y para cada i ≤ M Σj∈Ai lj ≤ C ? Codificación de las entradas: sobre el alfabeto Σ = {0, 1, ,}, los n+3 n´ umeros naturales que componen una entrada se escriben en binario y se separan por comas.


102

6. Subgrafo: Datos: G = (V, A), H = (V 0 , A0 ) dos grafos no dirigidos. Salida: ¿Es H un subgrafo de G?, es decir, ¿existe V1 ⊆ V y f : V1 → V 0 biyectiva tal que para cada u, v ∈ V1 , {u, v} ∈ A si y sólo si {f (u), f (v)} ∈ A0 ? Codificación de las entradas: sobre el alfabeto Σ = {0, 1, ,}, si x ∈ {0, 1}∗ es el n´ umero de vértices de G escrito en binario, y ∈ {0, 1}∗ es la matriz de adyacencia de G escrita por filas y z, t corresponden al n´ umero de vértices y matriz de adyacencia de H, entonces la codificación de la entrada G, H es la palabra x, y, z, t. ¿Están en EXP?

Cap´ıtulo 10

Reducciones en tiempo polin´ omico Referencia: Cap´ıtulo 2.5 de [GJ78]. En el cap´ıtulo 4 estudiamos las reducciones recursivas entre lenguajes, ≤m . Aqu´ı vamos a estudiar una parte de estas reducciones, las calculables en tiempo polinómico. En este caso daremos las definiciones para problemas decisionales codificados sobre un alfabeto cualquiera.

10.1.

Definici´ on

Definición 10.1 Dados dos alfabetos Σ y Γ, una función f : Σ∗ → Γ∗ es calculable en tiempo polinómico si existe un programa p que calcula f y una constante k ∈ IN tales que Tp (m) ∈ O(mk ). Nota: Si f es calculable en tiempo polinómico, entonces existen c, k tal que |f (x)| ≤ c|x|k para toda x. Definición 10.2 Sean A y B problemas decisionales con entradas codificadas sobre los alfabetos Σ y Γ respectivamente. Una reducción en tiempo polinómico de A en B es una función f : Σ∗ → Γ∗ que cumple: 1. f es calculable en tiempo polinómico. 2. Para todo x entrada de A:

103

´ CAPÍTULO 10. REDUCCIONES EN TIEMPO POLINOMICO

104

x tiene respuesta s´ı para A ⇔ f (x) tiene respuesta s´ı para B. Es decir, una reducción en tiempo polinómico es una reducción de L(A) en L(B) en el sentido definido en el cap´ıtulo 4, pero exigiendo que la reducción se pueda calcular en tiempo polinómico. Recordemos que L(Π) es el lenguaje asociado al problema decisional Π (cap´ıtulo 2). De hecho, la mayor´ıa de las reducciones vistas en el cap´ıtulo 4 son calculables en tiempo polinómico. Definición 10.3 Dados dos problemas decisionales A y B, A es reducible en tiempo polinómico a B si existe una reducción en tiempo polinómico de A en B. Lo denotamos con A ≤pm B.

10.2.

Primer ejemplo

Recordemos TSP, el problema del viajante, definido en el cap´ıtulo 7. Vamos a ver una primera reducción desde un problema de grafos, el problema del hamiltoniano (HAM), en el problema del viajante (TSP). Comenzamos dando unas definiciones sobre caminos para poder enunciar HAM. Definición 10.4 Dado un grafo no dirigido G = (V, A) con V = {1, . . . , n}, un camino es una secuencia de vértices C = (c1 , . . . , ck ) que cumple que para todo i desde 1 a k − 1, {ci , ci+1 } ∈ A. La longitud de un camino C = (c1 , . . . , ck ) es k − 1. Un camino C = (c1 , . . . , ck ) es simple si no tiene vértices repetidos, es decir, para todo i desde 1 hasta k, ci 6∈ {c1 , . . . , ci−1 , ci+1 , . . . , ck }. Un camino hamiltoniano es un camino simple de longitud n−1, es decir, un camino simple que pasa por todos los vértices. Un circuito es un camino C = (c1 , . . . , ck ) tal que {ck , c1 } ∈ A. Sea HAM el siguiente problema: Datos: G = (V, A) un grafo no dirigido con n vértices, Salida: ¿Tiene G un camino hamiltoniano? Codificamos la entrada con el alfabeto Σ = {0, 1, ,}, utilizando la codificación del grafo con matriz de adyacencia. Luego |G| = n2 .


105

Ejercicio. Demostrar que HAM ∈ NP. Para reducir HAM a TSP en tiempo polinómico queremos traducir cada entrada de HAM (un grafo no dirigido) en una entrada de TSP, es decir, un mapa de ciudades con sus distancias, de manera que el grafo original tenga un camino hamiltoniano si y sólo si el mapa tiene un camino corto que pasa por todas las ciudades. Para eso pondremos el mismo n´ umero de ciudades que vértices tiene el grafo y haremos la distancia entre dos ciudades peque˜ na si los correspondientes vértices están unidos con una arista, y grande en caso contrario, es decir, para cada G = (V, A) un grafo de n vértices, la reducción f se define como: f (G) = (n, d(i, j)(1 ≤ i ≤ n, 1 ≤ j ≤ n), n − 1) con

(

d(i, j) =

1 si {i, j} ∈ A 2n en otro caso.

Veamos que se trata de una reducción de HAM a TSP y que se puede calcular en tiempo polinómico. Para ver que es una reducción, sea G = (V, A) con V = {1, . . . , n} una entrada a HAM. Si G tiene solución s´ı para HAM, entonces G tiene un camino hamiltoniano C = (c1 , . . . , cn ). Luego para cada i desde 1 hasta n − 1, {ci , ci+1 } ∈ A. Por tanto para cada i desde 1 hasta n − 1, d(ci , ci+1 ) = 1 luego existe unPcamino, C, que pasa por las n ciudades una sola vez con longitud total n−1 i=1 d(ci , ci+1 ) = n−1 y por tanto f (G) = (n, d(i, j)(1 ≤ i ≤ n, 1 ≤ j ≤ n), n − 1) tiene solución s´ı para TSP. En la otra dirección, si f (G) tiene solución s´ı para TSP, existe un camino C = (c1 , . . . , cn ) que pasa por las n ciudades una sola vez con longitud total menor o igual que n − 1. Como d(i, j) es siempre mayor que 0, P para que n−1 i=1 d(ci , ci+1 ) ≤ n − 1 tiene que ser d(ci , ci+1 ) = 1 para cada i desde 1 hasta n − 1. Luego para cada i {ci , ci+1 } ∈ A, C es un camino de G y por no repetir vértices y ser de logitud n − 1 es un camino hamiltoniano, luego G tiene solución s´ı para HAM. El tiempo que tarda un programa en calcular f con una entrada G es n2 para calcular d más la instrucción de Devuelve, luego tp (G) ≤ n2 + 1. Como |G| ≥ n2 , Tp (m) ≤ m + 1 y por tanto f es calculable en tiempo polinómico.


10.3.

106

Propiedades elementales

Vamos a demostrar primero la propiedad que más nos interesará de las reducciones en tiempo polinómico, que es que si A ≤pm B y B ∈ P entonces A ∈ P. Esta propiedad es similar a la propiedad 4.5 y formaliza la idea de que si A ≤pm B entonces A es tanto o más fácil que B. Empezaremos con el siguiente lema. Lema 10.5 Sea h : IN → IN una funci´ on total creciente con h(m) ≥ m para todo m. Sean A y B dos problemas decisionales que cumplen 1. A ≤pm B y 2. B ∈ DTIME(h(m)). Entonces existen dos constantes c, k ∈ IN tales que A ∈ DTIME(h(cmk )). Dem. Sea p un programa que resuelve B en tiempo Tp (m) ≤ c1 · h(m) con c1 constante. Sea f una reducción de A en B calculable en tiempo polinómico. Sea q un programa que calcula f con Tq (m) ≤ c2 · mc3 , con c2 y c3 constantes. Por tanto para cada x entrada de A, |f (x)| ≤ |x| · c2 · |x|c3 . El siguiente algoritmo p0 resuelve A: Leer X Y:=ϕq (X); Z:=ϕp (Y); Devuelve Z. Vamos a acotar el tiempo de p0 con una entrada x: tp0 (x) ≤ tq (x) + tp (f (x)) ≤ c2 · |x|c3 + c1 · h(|f (x)|) ≤ ≤ h(c2 · |x|c3 ) + c1 · h(c2 · |x|c3 +1 ) (ya que h(m) ≥ m para todo m). Luego Tp0 (m) ≤ (c1 + 1)h(cmk ) con c = c2 y k = c3 + 1. Por tanto A ∈ DTIME(h(cmk )).


107

Luego si B ∈ P tenemos: Teorema 10.6 Sean A y B dos problemas decisionales tales que A ≤pm B. Entonces se cumple que: Si B ∈ P entonces A ∈ P. Dem. Si B ∈ DTIME(mk ), aplicamos el lema anterior para h(m) = mk . El teorema anterior se puede enunciar equivalentemente como: Teorema 10.7 Sean A y B dos problemas decisionales tales que A ≤pm B. Entonces se cumple que: Si A 6∈ P entonces B 6∈ P. lo que nos servirá para tratar con los problemas NP-completos (en el próximo cap´ıtulo). De manera análoga se demuestra el siguiente teorema: Teorema 10.8 Sean A y B dos problemas decisionales tales que A ≤pm B. Si B ∈ EXP entonces A ∈ EXP. El siguiente teorema demuestra que los problemas que están en P son reducibles en tiempo polinómico a todos los problemas. Intuitivamente esto quiere decir que seg´ un el orden marcado por las reducciones ≤pm los problemas en P son los más fáciles. Teorema 10.9 Sea A ∈ P. Sea B un problema decisional cualquiera no trivial, es decir, que no tiene la misma soluci´ on para todas las entradas. Entonces A ≤pm B Dem. Por ser B no trivial, tomo dos entradas fijas y1 , y2 tales que y1 tiene respuesta s´ı para B e y2 tiene respuesta no para B. Sean Σ y Γ los alfabetos que codifican las entradas de A y B respectivamente. Defino la función f : Σ∗ → Γ∗ como (

f (x) =

y1 y2

si x tiene solución s´ı para A si x tiene solución no para A

f es calculable en tiempo polinómico ya que la calcula el siguiente algoritmo, donde p es un programa para A con tp (x) ≤ c|x|k :


108

Leer X Simular(p,X,EXITO, Y); Si Y=SI entonces Devuelve y1 else Devuelve y2 . (En este algoritmo y1 e y2 son constantes.) f es claramente una reducción de A en B. La reducción ≤pm es transitiva, lo que utilizaremos en el siguiente cap´ıtulo: Teorema 10.10 Si A ≤pm B y B ≤pm C entonces A ≤pm C. Dem. Sea f una reducción en tiempo polinómico de A en B y g una reducción en tiempo polinómico de B en C. Entonces la composición de f y g, g ◦ f (x) = g(f (x)) es una reducción de A a C, ya que es cumple: x tiene solución s´ı para A ⇔ f (x) tiene solución s´ı para B ⇔ g(f (x)) = g ◦ f (x) tiene solución s´ı para C. Veamos que g ◦ f es calculable en tiempo polinómico. Si g es calculable 0 en tiempo Tp (m) ≤ cmk y f es calculable en tiempo Tq (m) ≤ c0 mk , entonces el algoritmo r: Leer X Y:=f (X); Z:=g(Y); Devuelve Z. funciona en tiempo 0

0

0

tr (x) ≤ c0 |x|k + c|f (x)|k ≤ c0 |x|k + c(c0 |x|k +1 )k ≤ 0 ≤ c00 |x|(k +1)k Definimos a continuación el concepto de ≤pm -dif´ıcil y ≤pm -completo para una clase: Definición 10.11 Dada una clase o conjunto de problemas decisionales C, un problema decisional X es ≤pm -dif´ıcil para C si para todo A ∈ C, A ≤pm X.


109

Definición 10.12 Dada una clase o conjunto de problemas decisionales C, un problema decisional X es ≤pm -completo para C si X es ≤pm -dif´ıcil para C y además X ∈C. Por la transitividad tenemos: Corolario 10.13 Sea X un problema decisional y sea V un problema ≤pm dif´ıcil para C. Si V ≤pm X entonces X es ≤pm -dif´ıcil para C. Dem. Sea A ∈C. Como sabemos que A ≤pm V y por hipótesis V ≤pm X, aplicando transitividad (teorema 10.10) tenemos que A ≤pm X. EJERCICIOS 10.1. Demostrar el Teorema 10.8.

Cap´ıtulo 11

Los problemas NP-completos Referencia: Cap´ıtulo 2 de [GJ78]. En este cap´ıtulo estudiaremos una serie de problemas para los cuales no se conocen algoritmos eficientes, es decir, no se sabe si están en P. Estos problemas están fuertemente relacionados entre s´ı, de manera que si uno de ellos estuviera en P entonces lo estar´ıan todos.

11.1.

El concepto de NP-completo

Empezaremos enunciando sin demostración el teorema de Cook, que dice que cualquier problema de la clase NP se puede reducir a SAT. Teorema 11.1 Para todo A ∈ NP se cumple que A ≤pm SAT. La demostración se puede ver en [HMU02] y en [GJ78]. Utilizando el teorema 10.6 tenemos la siguiente propiedad: Corolario 11.2 Si SAT ∈ P entonces cualquier A ∈ NP est´ a en P, luego NP ⊆ P. Como sabemos que P ⊆ NP (propiedad 9.13): Corolario 11.3 Si SAT ∈ P entonces P = NP. De otra forma: Corolario 11.4 Si P 6= NP entonces SAT 6∈ P. 110

CAPÍTULO 11. LOS PROBLEMAS NP-COMPLETOS

111

Como SAT∈ NP, si P = NP entonces SAT∈ P y por tanto: Corolario 11.5 Son equivalentes: a. P=NP b. SAT∈P De otra forma: Corolario 11.6 Son equivalentes: a. P6=NP b. SAT6∈P Podemos interpretar estas propiedades como “SAT tiene dificultad máxima en NP”, es decir, si existe un algoritmo eficiente para SAT entonces existen algoritmos eficientes para todos los problemas de NP. Existen muchos otros problemas en NP que comparten estas propiedades de SAT, son los NP-completos. Definición 11.7 Un problema se llama NP-dif´ıcil si es ≤pm -dif´ıcil para NP. Un problema se llama NP-completo si es ≤pm -completo para NP. Todos los NP-completos cumplen las anteriores propiedades de SAT (las demostraciones son análogas). Propiedad 11.8 Sea A un NP-completo. Si P 6= NP entonces A 6∈ P. Corolario 11.9 Sea A un NP-completo. Son equivalentes: a. P6=NP b. A6∈P Por tanto dados A y B NP-completos, son equivalentes: a. A6∈P b. B6∈P


112

ya que ambas afirmaciones son equivalentes a P6=NP. Sabemos pues de los problemas NP-completos que: Si un NP-completo no está P entonces ninguno está en P. No se conocen algorimos que funcionen en tiempo polinómico para ning´ un NP-completo. Por todo lo anterior, el que un problema A sea NP-completo se toma como una prueba de intratabilidad, en ese caso hay sospechas fundadas de que no existe un algoritmo eficiente que resuelva A. Para demostrar que un problema es NP-completo utilizaremos la siguiente propiedad, que se sigue del corolario 10.13: Propiedad 11.10 Sea A un problema NP-completo. Si B ∈NP y A ≤pm B entonces B es NP-completo. Luego como SAT es NP-completo, si demostramos que un problema B cumple: B ∈NP SAT≤pm B entonces ya sabemos que B es NP-completo. En adelante utilizaremos la u ´ltima propiedad para demostrar que nuevos problemas son NP-completos a partir de los que ya sepamos que lo son.

11.2.

Una reducci´ on complicada

En esta sección vamos a demostrar que 3-SAT, el problema que definimos a continuación, es NP-completo. Datos: Un conjunto de variables X y una fórmula CNF sobre X, L con exactamente 3 literales en cada cláusula (y que cumple que todas las variables de X aparecen al menos una vez en los literales de L, no hay cláusulas repetidas en L y dentro de cada cláusula no hay literales repetidos). Salida: ¿Existe una asignación de verdad que satisface L?


113

3-SAT tiene como entradas un subconjunto de las entradas de SAT, la fórmulas CNF que tienen exactamente tres literales por cláusula, y dada una entrada de 3-SAT, la solución para SAT y para 3-SAT es la misma. Codificaremos las entradas de 3-SAT de la misma forma que codificábamos las de SAT. Ejemplo 11.11 Una entrada de 3-SAT: X = {x1 , x2 , x3 }, L = (¬x2 ∨ x3 ∨ ¬x1 ) ∧ (x2 ∨ ¬x2 ∨ x1 ). Podr´ıa pensarse que al haber restringido las fórmulas, 3-SAT es más fácil que SAT. Veamos que no, ya que 3-SAT es también NP-completo. Para ello vemos primero que 3-SAT ∈ NP y después que SAT ≤pm 3-SAT. Teorema 11.12 3-SAT ∈ NP. Dem. Si tomamos el problema EVAL definido en el cap´ıtulo 9, sabemos que EVAL ∈ P y que si X, L es una entrada a 3-SAT y X, L, α es una entrada a EVAL entonces |X, L, α| ≤ 3|X, L|. Además como dada una entrada a 3-SAT X, L, su solución para SAT y para 3-SAT es la misma, entonces X, L tiene solución S´ı para 3-SAT ⇔ ∃α X, L, α tiene solución S´ı para EVAL

Teorema 11.13 SAT ≤pm 3-SAT. Dem. Para ver que SAT ≤pm 3-SAT, tenemos que definir una reducción computable en tiempo polinómico de SAT a 3-SAT, es decir, una función calculable en tiempo polinómico que transforme cada entrada de SAT X, L en f (X, L) = X 0 , L0 una entrada a 3-SAT, de forma que existe una asignación que satisface L si y sólo si existe una asignación que satisface L0 . Para definir f usamos la siguiente notación para los literales de una fórmula: Si X = {x1 , . . . , xn }, L = c1 ∧ . . . ∧ ck , donde c1 , . . . ck son cláusulas, entonces ci tiene ri literales z1i , . . . , zri i , o sea, ci = (z1i ∨ . . . ∨ zri i ).


114

Ejemplo 11.14 X = {x1 , x2 , x3 , x4 , x5 }, L = (¬x1 ) ∧ (x3 ∨ ¬x1 ∨ ¬x4 ∨ ¬x5 ∨ x2 ) Luego r1 = 1, r2 = 5, z11 = ¬x1 , z12 = x3 , z22 = ¬x1 , z32 = ¬x4 , z42 = ¬x5 , z52 = x2 . Vamos a transformar X, L en X 0 , L0 con X 0 = X ∪ ( ki=1 Yi ) con Yi nuevas variables a˜ nadidas para modificar la cláusula ci , L0 = ∧ki=1 Di donde cada Di es una fórmula CNF con tres literales por cláusula que sustituye a la cláusula ci de L. Definimos a continuación Yi , Di para cada i desde 1 hasta k: Si ri = 1 entonces Yi = {y1i , y2i } y S

Di = (z1i ∨ y1i ∨ y2i ) ∧ (z1i ∨ y1i ∨ ¬y2i ) ∧ (z1i ∨ ¬y1i ∨ y2i ) ∧ (z1i ∨ ¬y1i ∨ ¬y2i ) Si ri = 2 entonces Yi = {y1i } y Di = (z1i ∨ z2i ∨ y1i ) ∧ (z1i ∨ z2i ∨ ¬y1i ) Si ri = 3 entonces Yi = ∅ y Di = ci . Si ri > 3 entonces Yi = {y1i , . . . , yri i −3 } y Di =

(z1i ∨ z2i ∨ y1i ) ∧ (¬y1i ∨ z3i ∨ y2i ) ∧ (¬y2i ∨ z4i ∨ y3i ) ∧ . . . i i . . . ∧ (¬ys−2 ∨ zsi ∨ ys−1 ) ∧ . . . ∧ (¬yri i −4 ∨ zri i −2 ∨ yri i −3 ) ∧ ∧(¬yri i −3 ∨ zri i −1 ∨ zri i )

es decir, i i i −2 (¬ys−2 ∨ zsi ∨ ys−1 ) Di = (z1i ∨ z2i ∨ y1i ) ∧ (¬yri i −3 ∨ zri i −1 ∨ zri i ) ∧rs=3

Ejemplo 11.15 El ejemplo anterior queda transformado en X 0 = {x1 , x2 , x3 , x4 , x5 , y11 , y21 , y12 , y22 }, L0 = (¬x1 ∨ y11 ∨ y21 ) ∧ (¬x1 ∨ y11 ∨ ¬y21 ) ∧ (¬x1 ∨ ¬y11 ∨ y21 ) ∧(¬x1 ∨ ¬y11 ∨ ¬y21 ) ∧ (x3 ∨ ¬x1 ∨ y12 ) ∧ (¬y12 ∨ ¬x4 ∨ y22 ) ∧ (¬y22 ∨ ¬x5 ∨ x2 ) Veamos que existe una asignación que satisface L si y sólo si existe una asignación que satisface L0 .


115

⇒) Supongamos que existe una asignación α : X → {T, F } que satisface L. Definimos β : X 0 → {T, F } una asignación que satisface L0 como sigue: Si x ∈ X, β(x) = α(x). Si x ∈ Yi distinguimos tres casos: Si ri = 1 entonces β(y1i ) = β(y2i ) = T . Si ri = 2 entonces β(y1i ) = T . Si ri > 3 entonces como α satisface L, α satisface cada ci , luego existen uno o más literales de ci satisfechos por α. Sea j el primero tal que α satisface zji . • Si j ≤ 2 entonces β(ysi ) = F para todo s. • Si 2 < j < ri − 1 entonces: (

β(ysi )

=

T para 1 ≤ s ≤ j − 2 F para j − 1 ≤ s ≤ ri − 3

• Si j ≥ ri − 1 entonces β(ysi ) = T para todo s. Veamos que β satisface L0 viendo que satisface todas las Di para i desde 1 hasta k: a. Si ri = 1 entonces α satisface z1i , luego β satisface z1i y también Di Di = (z1i ∨ y1i ∨ y2i ) ∧ (z1i ∨ y1i ∨ ¬y2i ) ∧ (z1i ∨ ¬y1i ∨ y2i ) ∧ (z1i ∨ ¬y1i ∨ ¬y2i ) b. Si ri = 2 entonces α satisface (z1i ∨ z2i ), luego β también satisface Di = (z1i ∨ z2i ∨ y1i ) ∧ (z1i ∨ z2i ∨ ¬y1i ) c. Si ri > 3 entonces i i i −2 Di = (z1i ∨ z2i ∨ y1i ) ∧ (¬yri i −3 ∨ zri i −1 ∨ zri i ) ∧rs=3 (¬ys−2 ∨ zsi ∨ ys−1 )

sea j el primero tal que α satisface zji . i ∨ zji ∨ a) Si 2 < j < ri − 1 entonces β satisface la cláusula (¬yj−2 i yj−1 ) de Di . Son ciertas las ysi para 1 ≤ s ≤ j − 2 y falsas el i i resto, luego son ciertas las cláusulas (¬ys−1 ∨ zs+1 ∨ ysi ) para i i i 2 ≤ s ≤ j −2, las (¬ys ∨zs+2 ∨ys+1 ) para j −1 ≤ s ≤ ri −4, y las cláusulas primera y u ´ltima (z1i ∨ z2i ∨ y1i ), (¬yri i −3 ∨ zri i −1 ∨ zri i ).


116

b) Si j ≤ 2 β satisface la cláusula (z1i ∨ z2i ∨ y1i ) de Di y hemos hecho todas las ysi falsas, luego todas las cláusulas de la forma i i (¬ys−2 ∨ zsi ∨ ys−1 ) son ciertas y también la u ´ltima (¬yri i −3 ∨ zri i −1 ∨ zri i ). c) Si j ≥ ri − 1 β satisface la cláusula (¬yri i −3 ∨ zri i −1 ∨ zri i ) de Di . Todas las ysi son ciertas, luego son ciertas todas las cláusulas de i i ) y también la primera (z1i ∨ z2i ∨ y1i ). ∨ zsi ∨ ys−1 la forma (¬ys−2 ⇐) Supongamos que existe una asignación β : X 0 → {T, F } que satisface L0 , tomamos α : X → {T, F } como α(x) = β(x) para cada x ∈ X. Veamos que α satisface L, es decir, que satisface ci para todo i desde 1 a k. Si ri = 1 entonces β satisface las cuatro cláusulas (z1i ∨ y1i ∨ y2i ), (z1i ∨ y1i ∨ ¬y2i ), (z1i ∨ ¬y1i ∨ y2i ) y (z1i ∨ ¬y1i ∨ ¬y2i ). Como una de las cuatro cláusulas (y1i ∨ y2i ), (y1i ∨ ¬y2i ), (¬y1i ∨ y2i ), (¬y1i ∨ ¬y2i ) es falsa, necesariamente β hace cierto z1i y por tanto ci . Si ri = 2 entonces β satisface las dos cláusulas (z1i ∨ z2i ∨ y1i ) y (z1i ∨ z2i ∨ ¬y1i ), luego tiene que satisfacer (z1i ∨ z2i ) = ci . Si ri > 3 sea j el primero tal que β(yji ) = T , si no existe tal j entonces j = ri . Sea s el u ´ltimo tal que β(ysi ) = F , si no existe tal s entonces s = 0. Si j > 1 entonces β(y1i ) = F y por ser cierta la cláusula (z1i ∨z2i ∨y1i ) es cierta (z1i ∨ z2i ) y por tanto ci . Si s < ri − 3 entonces β(yri i −3 ) = T y por ser cierta la cláusula (¬yri i −3 ∨ zri i −1 ∨ zri i ) es cierta (zri i −1 ∨ zri i ) y por tanto ci . Si j = 1 y s = ri − 3 entonces existe un l con 1 ≤ l ≤ ri − 4 tal que i i i ) es ∨ yl+1 ) = F . Por tanto la cláusula (¬yli ∨ zl+2 β(yli ) = T , β(yl+1 i cierta por ser cierto zl+2 , luego β satisface ci . Para terminar falta ver que f es calculable en tiempo polinómico. Para calcular f sólo hace falta contar cláusulas y varibles de X, L y recorrer las cláusulas ci transformándolas en Di . Todo esto se puede hacer en tiempo tp (X, L) ≤

k X i=1

4ri


117

como cada ri ≤ 2n, tp (X, L) ≤ 8kn Como |X, L| ≥ k y |X, L| ≥ n, Tp (m) ≤ 8m2 .

11.3.

Algunos problemas NP-completos

Ya sabemos que SAT y 3-SAT son NP-completos. Vamos a ver aqu´ı cinco problemas más que también son NP-completos, lo cual nos permitirá demostrar que un nuevo problema es NP-completo utilizando la propiedad 11.10 y uno de los NP-completos ya conocidos. Comenzaremos enunciando los problemas VC y PARTICION. 11.3.1.

El problema del Vertex Cover

Este problema trata de cubrimientos de un grafo, que pasamos a definir. Definición 11.16 Dado un grafo no dirigido G = (V, A), un cubrimiento por vértices de G es un conjunto X ⊆ V tal que, para toda arista {u, v} ∈ A, u ∈ X ó v ∈ X. El problema VC o vertex cover trata de la existencia de cubrimientos peque˜ nos de un grafo: Datos: G = (V, A) un grafo no dirigido con n vértices, k ∈ IN con k ≤ n. Salida: ¿Existe un cubrimiento de G con k vértices? Codificamos la entrada como en el problema CLIQUE. Ejemplo 11.17 Sea G:

Este grafo tiene un cubrimiento de dos vértices, X = {3, 4}.


118

El problema VC tiene una estrecha relación con CLIQUE, ya que se cumple la siguiente propiedad: Propiedad 11.18 Sea G = (V, A) un grafo no dirigido, y sea X ⊆ V . Son equivalentes: 1. X es un cubrimiento de G. 2. V − X es un clique de Gc , donde Gc = (V, Ac ) con Ac = {{u, v} | {u, v} 6∈ A} Dem. 1.⇒2. Sea X un cubrimiento de G. Veamos que V − X es un clique de Gc . Sean u, v ∈ V − X, u 6= v. Entonces {u, v} 6∈ A, ya que ni u no v están en X, que es un cubrimiento de G. Por tanto {u, v} ∈ Ac . Esto se cumple para todo u, v ∈ V − X, u 6= v, luego V − X es clique de Gc . 2.⇒1. Sea X tal que V − X es clique de Gc . Veamos que X es un cubrimiento de G. Sea {u, v} ∈ A, u 6= v. Como {u, v} 6∈ Ac , al menos uno de los dos u, v no está en V − X que es un clique de Gc , luego al menos uno de los dos u, v está en X. Como eso se cumple para cada {u, v} ∈ A, X es un cubrimiento de G. Notemos que (Gc )c = G, luego tenemos el siguiente corolario que relaciona los problemas CLIQUE y VC. Corolario 11.19 Sea G un grafo no dirigido de n vértices. 1. G, k tiene solución s´ı para VC si y s´ olo si Gc , n − k tiene soluci´ on s´ı para CLIQUE. 2. G, k tiene solución s´ı para CLIQUE si y s´ olo si Gc , n − k tiene solución s´ı para VC. Luego tenemos el siguiente resultado Teorema 11.20 VC ≤pm CLIQUE y CLIQUE ≤pm VC. Dem. La función f (G, k) = Gc , n − k es reducción en los dos casos por la propiedad anterior. Para calcular f , sólo es necesario intercambiar ceros y unos en la matriz de adyacencia, lo cual se puede hacer en tiempo n2 , luego Tp (m) ≤ m (|G, k| ≥ n2 ) y f es calculable en tiempo polinómico.


119

También demostramos que VC ∈ NP. Teorema 11.21 VC ∈ NP. Dem. Sea compVC el siguiente problema: Datos: G = (V, A) grafo no dirigido, k ∈ IN, U subconjunto de V de k elementos. Salida: ¿Es U un cubrimiento de G ? Con las entradas codificadas como en compCLIQUE. Por tanto |G, k, U | ≥ n2 y |G, k, U | ≤ 5 · |G, k|. Un algoritmo para compVC es un u ńico bucle que para una entrada G, k, U comprueba si todas las parejas u, v con u, v ∈ V , u 6= v cumplen que si {u, v} ∈ A entonces u ∈ U ó v ∈ U . Si q es el algoritmo anterior, tq (G, k, U ) ≤ 2n2 Como |G, k, U | ≥ n2 , Tq (m) ≤ 2m, compVC ∈ DTIME(m) ⊆ P. Además por definición de compVC G, k tiene solución S´ı para VC ⇔ ∃U G, k, U tiene solución S´ı para compVC Luego VC ∈ NP. 11.3.2.

El problema PARTICION

El problema PARTICION se define como: Datos: n ∈ IN el n´ umero de objetos, p1 , . . . , pn ∈ IN los pesos de los objetos. Salida: ¿Existe un conjunto de objetos A ⊆ {1, . . . , n} que cumpla: X i∈A

pi =

X

pi ?

i6∈A

Esto es equivalente a decir, ¿existe un A tal que

P

i∈A

pi =

p1 +...+pn ? 2


120

Codificamos la entrada con el alfabeto Σ = {0, 1, ,}, cada natural en binario y separados por comas: n, p1 , . . . , pn Dejamos como ejercicio la demostración del siguiente teorema: Teorema 11.22 PARTICION ∈ NP. 11.3.3.

Siete NP-completos

Ya sabemos que SAT y 3-SAT son NP-completos. Vamos a ver que CLIQUE, VC, HAM, TSP y PARTICION también lo son partiendo del siguiente resultado, que no demostraremos. Teorema 11.23

3-SAT ≤pm PARTICION.

3-SAT ≤pm VC. VC ≤pm HAM. Corolario 11.24 PARTICION, VC y HAM son NP-completos. Dem. Sabemos que PARTICION, VC y HAM están en NP. A partir de que 3-SAT es NP-completo y de las dos primeras partes del teorema anterior tenemos que PARTICION y VC son NP-completos. Utilizando esto y la tercera parte del teorema anterior, HAM es NPcompleto. Utilizando dos reducciones ya conocidas Teorema 11.25 CLIQUE y TSP son NP-completos. Dem. Sabemos que CLIQUE y TSP están en NP (cap´ıtulo 9), y que HAM ≤pm TSP (cap´ıtulo 10) y VC ≤pm CLIQUE. Luego por el corolario anterior, CLIQUE y TSP son NP-completos. Nota: También son NP-completos los problemas dCLIQUE, dVC y dHAM cuyos enunciados son exactamente iguales a los de CLIQUE, VC y HAM excepto que el grafo de entrada es DIRIGIDO. El lector puede comprobar que estos tres nuevos problemas pertenecen a la clase NP. La demostración de que son NP-dif´ıciles no se tratará. EJERCICIOS


121

11.1. Demostrar que los siguientes problemas son NP-completos, sabiendo que lo son SAT, 3-SAT, VC, CLIQUE, HAM, TSP y PARTICION. 1. MOCHILA: Datos: n, p1 , . . . , pn , k, d ∈ IN Salida: ¿Existe A ⊆ {1, . . . , n} con k − d ≤ Σi∈A pi ≤ k ? Codificación de las entradas: sobre el alfabeto Σ = {0, 1, ,}, los n+3 n´ umeros naturales que componen una entrada se escriben en binario y se separan por comas. Pista: Reducir PARTICION. 2. Hitting-Set: Datos: n ∈ IN, A1 , . . . , Al subconjuntos de {1, . . . , n}, k ∈ IN Salida: ¿Existe A ⊆ {1, . . . , n} con #A ≤ k y para todo i ≤ l, Ai ∩ A 6= ∅? Codificación de las entradas: sobre el alfabeto Σ = {0, 1, ,}, n y k se escriben en binario, cada subconjunto de {1, . . . , n} se escribe con n bits (utilizando la secuencia caracter´ıstica) y los l + 2 datos se separan por comas. Pista: Reducir VC. 3. Multiprocessor Scheduling Datos: n ∈ IN el numero de tareas, l1 , . . . , ln el tiempo de cada tarea, M ∈ IN el n´ umero de procesadores C ∈ IN el tiempo máximo permitido Salida: ¿Podemos repartir la n tareas entre los M procesadores de manera que cada procesador tarde un tiempo menor o igual a C?, es decir, ¿Existen A1 , . . . , AM subconjuntos de {1, . . . , n} tales que A1 ∪ A2 . . . ∪ AM = {1, . . . , n} y para cada i ≤ M Σj∈Ai lj ≤ C ?


122

Codificación de las entradas: sobre el alfabeto Σ = {0, 1, ,}, los n+3 n´ umeros naturales que componen una entrada se escriben en binario y se separan por comas. Pista: Reducir PARTICION. 4. Partición en Hamiltonianos: Datos: G = (V, A) grafo no dirigido, k ∈ IN Salida: ¿Existen V1 , . . . , Vk tales que V1 ∪. . . Vk = V y para cada i ≤ k el subgrafo de vértices Vi tiene un camino hamiltoniano? Codificación de las entradas: sobre el alfabeto Σ = {0, 1, ,}, si x ∈ {0, 1}∗ es el n´ umero de vértices de G escrito en binario, y ∈ {0, 1}∗ es la matriz de adyacencia de G escrita por filas y z es k en binario, entonces la codificación de la entrada G, k es la palabra x, y, z. Pista: Reducir HAM. 5. Subgrafo: Datos: G = (V, A), H = (V 0 , A0 ) dos grafos no dirigidos. Salida: ¿Es H un subgrafo de G?, es decir, ¿existe V1 ⊆ V y f : V1 → V 0 biyectiva tal que para cada u, v ∈ V1 , {u, v} ∈ A si y sólo si {f (u), f (v)} ∈ A0 ? Codificación de las entradas: sobre el alfabeto Σ = {0, 1, ,}, si x ∈ {0, 1}∗ es el n´ umero de vértices de G escrito en binario, y ∈ {0, 1}∗ es la matriz de adyacencia de G escrita por filas y z, t corresponden al n´ umero de vértices y matriz de adyacencia de H, entonces la codificación de la entrada G, H es la palabra x, y, z, t. Pista: Reducir CLIQUE. G tiene un clique de k vértices si y sólo si el grafo completo de k vértices es subgrafo de G.

Cap´ıtulo 12

Ejercicios de examen 12.1.

Teor´ıa

1. Contestad Verdadero o Falso a cada una de las siguientes preguntas. ´ Las respuestas erróneas tienen puntuación negativa. ATENCION: Si A es un lenguaje decidible entonces A es semidecidible. Si A es un lenguaje semidecidible y B es un lenguaje indecidible entonces A ≤m B. Todo problema NP-completo está en NP. Si A ∈ P y B es un lenguaje decidible entonces A ≤m B. Si A ≤m B entonces B ≤m A La intersección de dos lenguajes semidecidibles es un lenguaje semidecidible. ¯ entonces A es decidible. Si A ≤m K y A ≤m K Si A es el dominio de una función calculable entonces A es semidecidible. Si K ≤m A entonces A es semidecidible. La intersección de dos lenguajes decidibles es un lenguaje decidible. Si A es el conjunto imagen de una función calculable entonces A es semidecidible. 123

CAPÍTULO 12. EJERCICIOS DE EXAMEN

124

La unión de dos lenguajes decidibles es un lenguaje decidible. NP ⊆ EXP. Si A ∈ P y B ∈ NP entonces A ≤pm B. Si A es un lenguaje semidecidible entonces A es el conjunto imagen de una función calculable. Si A es un lenguaje NO decidible y B es un lenguaje semidecidible entonces A ≤m B. La intersección de un lenguaje decidible y un lenguaje semidecidible es un lenguaje decidible. Si A ≤m K entonces A es semidecidible. Si A ∈ NP y B no es NP-dif´ıcil entonces A ≤pm B. Si A es NP-completo y B no es NP-dif´ıcil entonces A ≤pm B. Si A es el dominio de una función calculable entonces A es decidible. La unión de un lenguaje decidible y un lenguaje semidecidible es un lenguaje decidible. Si A es un lenguaje semidecidible entonces A es decidible. Si A ∈NP y B es NP-dif´ıcil entonces A ≤pm B. Si A es un lenguaje decidible entonces A es el dominio de una función calculable. Si L1 ∪L2 es decidible entonces L1 es decidible ó L2 es decidible. P ⊆ NP. Si A es un lenguaje decidible y B ∈ P entonces A ≤m B. La unión de dos lenguajes semidecidibles es un lenguaje semidecidible. SAT ∈ P y existe B ∈ NP − P. SAT está en EXP. 2. Sean A y B dos lenguajes o problemas decisionales. Demostrar la veracidad o falsedad de cada una de las siguientes afirmaciones. Si alguna de ellas es falsa, decir si es falsa en todos los casos o bien existen A y B para los cuales es cierta.


125

a. Si A es un lenguaje indecidible y B es un lenguaje semidecidible entonces A ≤m B. b. Si A es un lenguaje semidecidible y B es un lenguaje indecidible entonces A ≤m B. c. Si A es un lenguaje decidible y B ∈ P entonces A ≤m B. d. Si A ∈ P y B es un lenguaje decidible entonces A ≤m B. e. Si A ∈ P y B ∈ NP entonces A ≤pm B. f. Si A ∈ NP y B no es NP-dif´ıcil entonces A ≤pm B. g. Si A es NP-completo y B no es NP-dif´ıcil entonces A ≤pm B. 3. Demostrar la veracidad o falsedad de cada una de las siguientes afirmaciones: a. Si A es un lenguaje decidible entonces A es el dominio de una función calculable. b. Si A es el dominio de una función calculable entonces A es decidible. c. Si A es un lenguaje semidecidible entonces A es el conjunto imagen de una función calculable. d. Si A es el conjunto imagen de una función calculable entonces A es semidecidible. 4.

Demostrar que P ⊆ NP. Demostrar que las siguientes afirmaciones son equivalentes para un lenguaje A: a. A es semidecidible. b. Existe un lenguaje B decidible tal que para cualquier x x ∈ A ⇐⇒ ∃ t x, t ∈ B

5. Para los siguientes conjuntos de problemas decisionales: NP, P, SEMIDEC, EXP, NP-completos, DEC (SEMIDEC son los problemas semidecidibles, DEC los decidibles)


126

a. ¿Qué contenidos sabes que se cumplen entre los conjuntos anteriores? Para cada uno de ellos, explicar porqué. b. ¿Qué contenidos sabes que NO se cumplen entre los conjuntos anteriores? Para cada uno de ellos, explicar porqué. 6. ¿Es correcta la siguiente demostración de que HAM 6∈ P? Razonar la respuesta. Consideramos el siguiente algoritmo para SAT: “Con entrada X, F , probar todas las posibles asignaciones de las variables de X. Si alguna hace cierta F devuelve S´ı, en caso contrario devuelve No.” Este algoritmo requiere claramente tiempo exponencial. Por tanto SAT no está en P. Como SAT ≤pm HAM, debe cumplirse que HAM 6∈ P. 7. Definir los siguientes conceptos: a. Máquina de Turing b. Función calculada por una máquina de Turing. 8. ¿Qué función calcula la máquina de Turing M = (Q, Σ, Γ, δ, q0 , qF ) con Q = {q0 , qC , qA , qB , qF }, Σ = {0, 1}, Γ = {0, 1, ., b} y δ definida como: δ(q0 , 0) δ(q0 , 1) δ(q0 , b) δ(qC , 0) δ(qC , 1) δ(qC , .) δ(qA , 0) δ(qB , 0) δ(qB , b)

= = = = = = = = =

(q0 , 0, d) (q0 , 1, d) (qC , b, i) (qF , 1, n) (qC , 0, i) (qA , ., d) (qB , 1, d) (qB , 0, d) (qF , 0, n) ?

9. Para cada una de las siguientes afirmaciones, decir si es cierta o falsa, razonándolo en cualquiera de los dos casos. Se puede utilizar cualquier propiedad vista en clase, enunciándola adecuadamente.


127

(DEC es el conjunto de los lenguajes decidibles, SEMIDEC es el conjunto de los lenguajes semidecidibles.) a. b. c. d.

SEMIDEC ⊆ DEC NP ⊆ P Si A ∈ P y B ∈ NP entonces A ∪ B ∈ NP Si K ≤m A entonces A es semidecidible

10. En la asignatura de Metodolog´ıa de la Programación los alumnos deben realizar una práctica 0 que consiste en escribir un programa en ada que calcule la suma de dos n´ umeros enteros. a. ¿Puede el profesor corregir automáticamente las prácticas, es decir, hacer un programa que toma como entrada un fuente ada cualquiera y dice si calcula la suma correctamente o no? b. Si se impone la condición adicional de que el fuente debe tener menos de 100 caracteres, ¿cuál es la respuesta de a)? En los dos apartados hay que demostrar la respuesta, tanto si esta es afirmativa como si es negativa. 11. Encontrar el fallo en la siguiente demostración errónea de P6=NP: Consideramos el siguiente algoritmo para SAT: “Con entrada X, F , probar todas las posibles asignaciones de las variables de X. Si alguna hace cierta F devuelve S´ı, en caso contrario devuelve No.” Este algoritmo requiere claramente tiempo exponencial. Por tanto SAT no está en P. Como SAT está en NP, debe cumplirse que P no es igual a NP. 12. Acabas de empezar a trabajar como analista jefe para la compa˜ n´ıa Comunicaciones Universales S.A., que tiene un total de 500.000 centrales telefónicas en esta galaxia. En cada momento algunas conexiones entre centrales pueden fallar, as´ı que tu primer encargo consiste en dise˜ nar un algoritmo que dado un mapa de las conexiones que funcionan en un momento dado, dé el camino más corto que pase por todas las centrales, sin pasar dos veces por ninguna. Después de varios d´ıas de trabajo entusiasta, empiezas a desanimarte al ver que el mejor algoritmo que se te ocurre puede llegar a tardar 10100000 a˜ nos en resolver el problema.


128

Al d´ıa siguiente vas al despacho del jefe con un libro de complejidad en la mano y con la intención de convencerle de que redefina el problema (por ejemplo, ¿no le bastar´ıa un camino cualquiera? o ¿los mapas de conexiones son de alg´ un tipo especial?). Explica de manera formal esta conversación con el jefe (es importante que le convenzas de que t´ u no eres un mal programador). 13.

a. Definir la clase NP. b. Demostrar que NP ⊆ EXP.

14. Desarrollar las siguientes cuestiones (con demostraciones): a. Definir los conceptos de: a) función calculable, b) lenguaje decidible, c) lenguaje semidecidible. b. Relación entre los conceptos de lenguaje decidible y lenguaje semidecidible. c. Comportamiento de los lenguajes decidibles y semidecidibles con las operaciones de unión e intersección. 15. Sea 6-SAT el siguiente problema: Datos: Un conjunto de variables X y una fórmula CNF sobre X, L con exactamente 6 literales por cláusula (y cumpliendo que todas las variables de X aparecen al menos una vez en los literales de L, no hay cláusulas repetidas en L y dentro de cada cláusula no hay literales repetidos). Salida: ¿Existe una asignación de verdad que satisface L? Codificación de las entradas: La misma que la de las entradas de SAT. Demostrar que 6-SAT ≤pm 3-SAT, utilizando una versión simplificada de la reducción de SAT a 3-SAT. 16. Sean H y K las dos versiones del problema de parada. Demostrar las siguientes afirmaciones: a. H no es decidible, y tampoco lo es K. b. H y K son ambos semidecidibles


129

¯ ni K ¯ son semidecidibles. c. Ni H En la realización de este ejercicio no debe utilizarse NINGUN resultado que no se demuestre. 17. Contestar a cada una de las siguientes cuestiones, razonando la respuesta. En dicha respuesta se puede utilizar cualquier propiedad vista en clase, enunciándola adecuadamente. a. ¿Todo problema NP-completo está en P? b. ¿SAT está en EXP? c. ¿La unión de un lenguaje decidible y un lenguaje semidecidible es un lenguaje decidible? d. ¿Si A ≤m B entonces B ≤m A? ¯ entonces A es decidible? e. ¿Si A ≤m K y A ≤m K 18. Enunciar el teorema de Rice. Explicar su significado y utilidad. Demostrar dicho teorema. 19. Para cada una de las siguientes afirmaciones, decir si es cierta o falsa, razonándolo en cualquiera de los dos casos. (DEC es el conjunto de los lenguajes decidibles, SEMIDEC es el conjunto de los lenguajes semidecidibles. L1 y L2 son dos lenguajes cualesquiera.) a. DEC ⊆ SEMIDEC b. SEMIDEC ⊆ DEC c. SAT ∈ P y existe B ∈ NP − P. d. Si L1 ∪L2 es decidible entonces L1 es decidible ó L2 es decidible. e. Sea A ∈ EXP un problema con entradas codificadas sobre Σ = {0, 1}, definimos el siguiente lenguaje sobre Σ: LA = {w | w codifica una entrada con salida SI para A} Entonces LA es un lenguaje decidible. Nota.- Se puede utilizar sin necesidad de demostrarlo el teorema de Cook (referente al problema SAT), y la clausura de P por ≤pm .


20.

130

a. Describir un modelo abstracto de cálculo (que no sea la máquina de registros ó RAM). b. Enunciar la tesis de Turing-Church y explicar su significado. c. Enunciar la tesis extendida de Turing-Church y explicar su significado.

21. La profesora de Ciencias del Conocimiento ha decidido dar como proyecto el dise˜ no de un algoritmo que, dados un programa p y una entrada x, determine (contestando SI ó NO) si p con entrada x se parará en un tiempo que sea m´ ultiplo de 6 (en 6 pasos, ó en 12, 18, 24, etc.). El estudiante Manolito (que tiene sobresaliente en MAC) le dice que es imposible encontrar tal algoritmo. Después de consultarlo con los esp´ıritus, la profesora decide cambiar el problema por el de dise˜ nar un algoritmo que, dados un programa p y una entrada x, determine (contestando SI ó NO) si p con entrada x se parará en un tiempo menor o igual que 3000 y que sea m´ ultiplo de 6. Con esto Manolito ya está satisfecho. Explicar detalladamente (con las demostraciones formales necesarias) el razonamiento de Manolito y por qué la profesora hace este cambio que convence a Manolito. Pista: Dado un programa, es fácil construir otro que haga lo mismo en tiempo m´ ultiplo de 6. Si utilizas esto en alg´ un momento de tu demostración, pruébalo.

12.2.

Problemas de computabilidad

22. Sea A = {x, y |Dom(ϕx ) = {2z | z ∈ Im(ϕy )} } ¿Es A decidible? ¿Es A semidecidible? ¿Es A¯ semidecidible? 23. Sea A = {x, y |

∀n(Si y(n)↓ entonces x(n)↓ en ϕy (n) pasos o menos)}


131

¿Es A decidible? ¿Es A semidecidible? ¿Es A¯ semidecidible? 24.

a. ¿Existe un algoritmo que resuelva el siguiente problema? Datos: p, y, k, donde p es un programa, y es una cadena y k un n´ umero natural. Salida: ¿Existen al menos k entradas distintas de p que dan salida y? b. Sea A = {x | ∃n > 5 (x(n)↑ ∨ (x(n)↓ en más de n pasos))} ¿Es A decidible? ¿Es A semidecidible? ¿Es A¯ semidecidible? c. ¿Existe un algoritmo que resuelva el siguiente problema? Datos: p, donde p es un programa. Salida: ¿Existe un programa sin llamadas a procedimientos de menos de 100 caracteres que calcula exactamente lo mismo que p?

25. Sea A el siguiente lenguaje: A = {x, y | ∃n ( x(n)↓ ∧ y(n)↑ )} a. ¿Es A decidible? ¿Es A semidecidible? b. ¿Es A¯ semidecidible? 26. Sea A el siguiente lenguaje: A = {x | ∀n ( x(n) ↓ ∧ (ϕx (n) < ϕx (n + 1)) )} a. ¿Es A decidible? ¿Es A semidecidible? b. ¿Es A¯ semidecidible? 27. Sean L1 , L2 los siguientes lenguajes: L1 = {x, y | Dom(ϕx ) 6= Dom(ϕy )}, L2 = {z | ∀x z(x) ↓ y ϕϕz (x) es total}. ¯ 1 semidecidible? a. ¿Es L1 decidible? ¿Es L1 semidecidible? ¿Es L ¯ 2 semidecidible? b. ¿Es L2 decidible? ¿Es L2 semidecidible? ¿Es L


132

28. Sean L1 , L2 los siguientes lenguajes: L1 = {m, n | m(n) ↓ y tarda tiempo m´ ultiplo de n}, L2 = {z | ∀x z(x) ejecuta la antepen´ ultima instrucción de z}. ¯ 1 semidecidible? a. ¿Es L1 decidible? ¿Es L1 semidecidible? ¿Es L ¯ 2 semidecidible? b. ¿Es L2 decidible? ¿Es L2 semidecidible? ¿Es L 29. Demostrar que el siguiente problema no es resoluble con nig´ un programa: Datos: Sean p y q dos programas con su codificación habitual. Salida: ¿p y q hacen exactamente lo mismo, es decir, para cada entrada se cumple que o bien no da salida ninguno de los dos programas o bien ambos dan la misma salida? 30. Sea L el siguiente lenguaje: L = {x | Im(ϕx ) es infinito}. a. ¿Es L semidecidible? ¯ semidecidible? b. ¿Es L 31. Sean L1 , L2 los siguientes lenguajes: L1 = {z | ∃x, y z(x, y) 6= x + y}, L2 = {x, y | ϕx (y) = ϕy (y) + 1}. a. ¿Es L1 decidible? ¿Es ¯ 1 decidible? ¿Es b. ¿Es L c. ¿Es L2 decidible? ¿Es

L1 semidecidible? ¯ 1 semidecidible? L L2 semidecidible?

32. Sean A y B los siguientes lenguajes: A = {x | ∀n ϕx (n) = n + 1} B = {x | Dom(ϕx ) contiene alg´ un n´ umero primo}. a. ¿Es A decidible? ¿Es A semidecidible? ¿Es A¯ semidecidible? ¯ semidecidible? b. ¿Es B decidible? ¿Es B semidecidible? ¿Es B


133

33. Sean A y B los siguientes lenguajes: A = {x | ∃y y ∈ Dom(ϕx ) ∧ Dom(ϕy ) 6= ∅} B = {x | ∃y y ∈ Dom(ϕx ) ∧ x ∈ Dom(ϕy )}. a. ¿Es A decidible? ¿Es A semidecidible? b. ¿Es B decidible? ¿Es B semidecidible? c. ¿Es A¯ semidecidible? 34. Sea A el siguiente lenguaje: A = {x | ∀n x(2n)↓ si y sólo si x(2n + 1)↓}. a. ¿Es A decidible? b. ¿Es A semidecidible? c. ¿Es A¯ semidecidible? 35. Sean L1 , L2 los siguientes lenguajes: L1 = {x | Dom(ϕx ) contiene todos los n´ umeros pares}, L2 = {x, y | ∃z ϕz (x) = y}. ¯ 1 semidecidible? a. ¿Es L1 decidible? ¿Es L1 semidecidible? ¿Es L b. ¿Es L2 decidible? ¿Es L2 semidecidible? 36. Sean L1 , L2 los siguientes lenguajes: L1 = {z | ∀x ϕz (x) es un n´ umero par}, L2 = {z, y | ∃x > y ϕz (x) es un n´ umero par}. a. ¿Es L1 decidible? ¿Es L1 semidecidible? ¯ 1 decidible? ¿Es L ¯ 1 semidecidible? b. ¿Es L c. ¿Es L2 decidible? ¿Es L2 semidecidible? 37. Sean L1 y L2 los siguientes lenguajes: L1 = {z | ∃x ϕz (x) es un n´ umero primo}, L2 = {x | x(x)↓ en tiempo menor o igual que x2 }.


134

¯ 1 semidecidible? a. ¿Es L1 decidible? ¿Es L1 semidecidible? ¿Es L ¯ 2 semidecidible? b. ¿Es L2 decidible? ¿Es L2 semidecidible? ¿Es L 38. Sean L1 y L2 los siguientes lenguajes: L1 = {x | Im(ϕx ) no contiene ning´ un n´ umero par}, L2 = {z, x | ∃y ϕz (y) > x}. ¯ 1 semidecidible? a. ¿Es L1 decidible? ¿Es L1 semidecidible? ¿Es L ¯ 2 semidecidible? b. ¿Es L2 decidible? ¿Es L2 semidecidible? ¿Es L 39. Sean L1 y L2 los siguientes lenguajes: L1 = {x | x calcula la función identidad}, L2 = {x, y | ϕx ≡ ϕy }. ¯ 1 semidecidible? a. ¿Es L1 decidible? ¿Es L1 semidecidible? ¿Es L ¯ 2 semidecidible? b. ¿Es L2 decidible? ¿Es L2 semidecidible? ¿Es L 40. Sean L1 y L2 los siguientes lenguajes: L1 = {z | ∃x ϕz (x) es m´ ultiplo de 7 }, L2 = { x, y |

al ejecutar x con entrada y, en alg´ un IF-THEN-ELSE se toma la opción else }.

a. ¿Es L1 decidible? ¿Es L1 semidecidible? ¯ 2 semidecidible? b. ¿Es L2 decidible? ¿Es L2 semidecidible? ¿Es L 41. Sean L1 y L2 los siguientes lenguajes: L1 = {x | K ⊆ Dom(ϕx )}, L2 = {u, v, w | u(v) ↓ ∧ v(w) ↓ ∧ ϕu (v) = (ϕv (w))2 }. a. ¿Es L1 decidible? ¿Es L1 semidecidible? b. ¿Es L2 decidible? ¿Es L2 semidecidible? 42. Sean L1 y L2 los siguientes lenguajes: L1 = {x | Dom(ϕx ) es finito }, L2 = {z, y | ∃x < y z(x) ↓}.


135

a. ¿Es L1 decidible? ¿Es L1 semidecidible? b. ¿Es L2 decidible? ¿Es L2 semidecidible? 43. Sea f una función TOTAL que cumple: f (x) = ϕx (x)

si x ∈ K

¿Es f calculable? Pista: Estudiar el lenguaje A = {x | ϕx (x) = n´ umero de pasos en la ejecución de x con entrada x}. 44. Sea calc el conjunto de todas las funciones calculables. Sean g, h funciones calculables tales que Dom(g) = ∅. Sea H =calc−{h}. a. Sea L un lenguaje tal que INDg ⊆ L ⊆ INDH ¿Es L decidible? ¿Es L semidecidible? b. Sea A el lenguaje: A = { x | x(5x + 1) ↑ }. ¿Es A decidible? ¿Es A semidecidible? 45. Dado Π el problema que se enuncia a continuación, ¿existe un programa que resuelve Π? Datos: p, x, k Salida: ¿En la ejecución del programa codificado por p con la entrada codificada por x, se repite la pen´ ultima instrucción del fuente al menos k veces? Codificaci´ on de las entradas: sobre el alfabeto {0, 1}, con la codificación usual de programas, entradas y n´ umeros naturales. 46. Sean L1 y L2 los siguientes lenguajes: L1 = {x | ∃ y tal que ϕx ≡ ϕy y x 6= y}, L2 = {z, n | ∃ x tal que ϕz (x) = 1 y |x| = n}.


136

a. ¿Es L1 decidible? ¿Es L2 decidible? b. ¿Es L2 semidecidible? c. Sea f la función definida como: f (x) = x + 5 si x 6∈ L2 ¿Es f calculable? 47. Sean L1 y L2 los siguientes lenguajes: L1 = {x | ϕx (5) 6= 30}, L2 = {z, x, t | z codifica un programa que, con entrada x, para en tiempo menor o igual que t}. a. ¿Es L1 decidible? ¿Es L2 decidible? b. ¿Es L1 semidecidible? c. Sea f la función definida como: f (x) = x + 5 si x 6∈ L1 ¿Existe una máquina de Turing que calcule f ? 48. Sean L1 y L2 los siguientes lenguajes: L1 = { x | Im(ϕx ) = Dom(ϕx ) }, L2 = { x, y | Im(ϕx ) = Dom(ϕy ) }. a. ¿Es L1 decidible? b. ¿Es L2 semidecidible? c. Sea χL1 la función caracter´ıstica de L1 . ¿Existe una máquina de Turing que calcule χL1 ? ¿Existe una máquina de Turing que calcule χL2 ?


12.3.

137

Problemas de complejidad

49. Sea X el siguiente problema. Demostrar que es NP-completo. Datos: G = (V, A) un grafo NO DIRIGIDO de n vértices, k ∈ IN con k ≤ n. Salida: ¿Existe un conjunto de k vértices U ⊆ V tal que para todo u, v ∈ U se cumple que {u, v} 6∈ A? Codificaci´ on de las entradas: Sobre el alfabeto Σ = {0, 1, ,}, si r ∈ {0, 1}∗ es el n´ umero de vértices escrito en binario, s ∈ ∗ {0, 1} es la matriz de adyacencia de G escrita por filas, y x es k en binario, entonces la codificación de la entrada G, k es la palabra r, s, x. 50. Sea X el siguiente problema. Demostrar que es NP-completo. Datos: n, m, p1 , . . . , pn , v1 , . . . , vn , B, K ∈ IN, U1 , . . . , Um subconjuntos disjuntos de {1, . . . , n} tales que U1 ∪ . . . ∪ Um = {1, . . . , n}. Salida: ¿Existe un conjunto A ⊆ {1, . . . , n} que contenga como mucho un elemento de cada conjunto Ui (kA ∩ Ui k ≤ 1 ∀i) y que cumpla las siguientes condiciones: X

pj ≤ B

j∈A

X

vj ≥ K

j∈A

Codificaci´ on de las entradas: Sobre el alfabeto Σ = {0, 1, ,}, los 2n+4 n´ umeros naturales se escriben en binario y se separan por comas, seguidos de los m subconjuntos codificados cada uno con n bits y separados por comas. 51.

a. Sea X el siguiente problema. Demostrar que es NP-completo. Datos: G, donde G es un grafo dirigido de n vértices. Salida: ¿Existe un camino de G con longitud n que pase por todos los vértices de G (es decir, un camino que pase por uno de los vértices 2 veces y por todos los demás una vez)?


138

Codificaci´ on de las entradas: Utilizando la matriz de adyacencia del grafo. b. Sea Y el siguiente problema. Demostrar que es NP-completo. Datos: G, k, donde G es un grafo dirigido de n vértices y k es un n´ umero natural con k ≤ n. Salida: ¿Existe un camino de G que pase por uno de los vértices exactamente k veces y por todos los demás una sola vez? Codificaci´ on de las entradas: Utilizando la matriz de adyacencia del grafo. 52. Sea NUMSAT el siguiente problema. Demostrar que es NP-completo. Datos: X, F, k, donde X es un conjunto de n variables, F una fórmula booleana sobre X en forma normal conjuntiva (es decir, escrita como conjunción de cláusulas) y k es un n´ umero natural k ≤ n. Salida: ¿Existen al menos k asignaciones distintas de X que hacen cierta F ? Codificaci´ on de las entradas: La misma que la de las entradas de SAT. 53. Sea 2dHAM el siguiente problema. Demostrar que es NP-completo. Datos: G = (V, A) un grafo DIRIGIDO. Salida: ¿¿G tiene más de un camino hamiltoniano? Codificación de las entradas: Utilizando listas de adyacencia. 54. Sea CUBRECICLOS el siguiente problema. Demostrar que es NPcompleto. Datos: G = (V, A) un grafo dirigido, k ∈ IN con k ≤ n (donde n es el n´ umero de vértices de G). Salida: ¿Existe un conjunto de k vértices U ⊆ V que cubre todos los circuitos de G? (U cubre todos los circuitos de G si para todo c1 , . . . , ca circuito de G existe alg´ un i entre 1 y a con ci ∈ U ).


139

Codificaci´ on de las entradas: Utilizando la matriz de adyacencia del grafo. Pista: utilizar dVERTEX COVER. 55. Sea INECUACIONES el siguiente problema. Demostrar que es NPcompleto. Datos: n ∈ IN el n´ umero de inecuaciones, m ∈ IN el n´ umero de incógnitas, ai,j ∈ Q para cada 1 ≤ i ≤ n, 0 ≤ j ≤ m los coeficientes racionales, σi ∈ {≤, ≥} para cada 1 ≤ i ≤ n, las desigualdades de las inecuaciones. (Por ejemplo para −7/3 + 3x1 ≥ 0, es ≥) Salida: ¿Existe una solución al sistema de inecuaciones formada sólo por ceros y unos? Es decir, v1 , . . . , vm ∈ {0, 1} que cumplan a1,0 + a1,1 v1 + a1,2 v2 + . . . + a1,m vm σ1 0 a2,0 + a2,1 v1 + a2,2 v2 + . . . + a2,m vm σ2 0 ... an,0 + an,1 v1 + an,2 v2 + . . . + an,m vm σn 0 Codificación de las entradas: sobre el alfabeto Σ = {0, 1, ,, (, ), ≤, ≥ }, se escriben los n´ umeros racionales como (a, b, s), a y b numerador y denominador en binario y s un bit extra para el signo, los naturales en binario, las desigualdades con el s´ımbolo correspondiente y todos ellos separados por comas. Pista: utilizar MOCHILA o PARTICION. 56. Sea GTSP (problema del viajante generalizado) el siguiente problema: Datos: n ∈ IN el n´ umero de ciudades, d(i, j) ∈ IN para cada 1 ≤ i, j ≤ n las distancias entre cada dos ciudades (tales que d(i, j) = d(j, i) y d(i, i) = 0 para todo i, j),


140

k ∈ IN. Salida: ¿Existe un camino cualquiera (se iten repeticiones) que pasa por todas las ciudades y que tiene una longitud total menor o igual que k? Codificación de las entradas: sobre el alfabeto Σ = {0, 1, ,}, se escriben los n´ umeros naturales en binario y separados por comas. Demostrar que GTSP es NP-dif´ıcil (es decir, que A ≤pm GTSP para alg´ un NP-completo A). Pista: TSP no es una buena elección para esta reducción. 57. Sea IPL (programación lineal entera) el siguiente problema. Datos: n ∈ IN el n´ umero de ecuaciones, m ∈ IN el n´ umero de incógnitas, ai,j ∈ Z para cada 1 ≤ i ≤ n, 0 ≤ j ≤ m los coeficientes enteros, c ∈ IN. Salida: ¿Existe una solución entera v1 , . . . , vm ∈ Z al sistema de inecuaciones: a1,0 + a1,1 x1 + a1,2 x2 + . . . + a1,m xm ≥ 0 a2,0 + a2,1 x1 + a2,2 x2 + . . . + a2,m xm ≥ 0 ... an,0 + an,1 x1 + an,2 x2 + . . . + an,m xm ≥ 0 que cumpla valor absoluto(vj ) ≤ c para 1 ≤ j ≤ m? Codificación de las entradas: sobre el alfabeto Σ = {0, 1, ,}, se escriben los n´ umeros en binario (con un bit extra para el signo) y separados por comas. Demostrar que IPL ∈ NP. 58. Sea CAMINO GUIADO el siguiente problema. Demostrar que es NP-completo. CAMINO GUIADO Datos: G un grafo NO DIRIGIDO de n vértices k ∈ IN con 2 ≤ k ≤ n.


141

v1 , . . . , vk , k vértices distintos de G. Salida: ¿Existe C = (c1 , . . . , cn ) un camino hamiltoniano de G y existen 1 = i1 < i2 < . . . < ik = n de forma que v1 = ci1 , v2 = ci2 , . . . , vk = cik (es decir, C empieza en v1 , pasa siempre por vj antes que por vj+1 y acaba en vk )? Codificación de las entradas: sobre el alfabeto Σ = {0, 1, ,}, se escribe el n´ umero de vértices en binario, seguido de coma, seguido de la matriz de adyacencia de G escrita por filas, seguido de coma y por u ´ltimo k, v1 , . . . , vk en binario y separados por comas. 59. Sean SATGRAL y SATSIMPL los siguientes problemas. Demostrar que ambos son NP-completos. SATGRAL Datos: X, F , donde X = {x1 , . . . , xn } es un conjunto de variables y F una fórmula booleana cualquiera escrita con las variables de X, conectivas ∧, ∨, ¬ y los paréntesis necesarios. Salida: ¿Existe una asignación de X que hace cierta F ? Codificación de las entradas: Sobre el alfabeto {∧, ∨, ¬, (, ), 0, 1} codificando cada variable por su n´ umero en binario y las conectivas y paréntesis con los s´ımbolos correspondientes. Por ejemplo (x5 ∨ (x1 ∧ (¬x6 ∨ x4 ))) se codifica como (101 ∨ (1 ∧ (¬110 ∨ 100))) SATSIMPL Datos: X, F , donde X es un conjunto de variables, y F una fórmula booleana en forma normal conjuntiva (es decir, escrita como conjunción de cláusulas), y tal que en ninguna cláusula aparece la misma variable más de una vez. Salida: ¿Existe una asignación de X que hace cierta F ? Codificación de las entradas: La misma que la de las entradas de SAT. 60. Sea 3HAM el siguiente problema. Demostrar que es NP-completo. 3HAM


142

Datos: G un grafo NO DIRIGIDO de n vértices a, b, c, tres vértices de G. Salida: ¿Existe un camino hamiltoniano de G (es decir, un camino simple que pasa por todos los vértices) que empiece en el vértice a, acabe en el vértice c, y tenga el vértice b en la posición central (es decir, en el lugar bn/2c)? Codificación de las entradas: sobre el alfabeto Σ = {0, 1, ,}, si u ∈ {0, 1}∗ es el n´ umero de vértices escrito en binario, v ∈ {0, 1}∗ es la matriz de adyacencia de G escrita por filas, y x, y, z ∈ {0, 1}∗ son a, b y c en binario, entonces la codificación de la entrada G, a, b, c es la palabra u, v, x, y, z. 61. Sean MPATH y SPATH los siguientes problemas: MPATH Datos: G un grafo NO DIRIGIDO, r, s, dos vértices de G, k ∈ IN con k ≤ n. Salida: ¿Existe un camino simple de G (es decir, sin vértices repetidos) de longitud ≥ k que empiece en el vértice r y acabe en el vértice s? SPATH Datos: G un grafo NO DIRIGIDO, r, s, dos vértices de G, k ∈ IN con k ≤ n. Salida: ¿Existe un camino simple de G (es decir, sin vértices repetidos) de longitud ≤ k que empiece en el vértice r y acabe en el vértice s? Codificación de las entradas: sobre el alfabeto Σ = {0, 1, ,}, si u ∈ {0, 1}∗ es el n´ umero de vértices escrito en binario, v ∈ {0, 1}∗ es la matriz de adyacencia de G escrita por filas, y x, y, z ∈ {0, 1}∗ son r y s y k en binario, entonces la codificación de la entrada G, r, s, k es la palabra u, v, x, y, z.


143

a. Demostrar que MPATH es NP-completo. Pista para a): comparar con HAM. b. Demostrar que SPATH ∈ P. Pista para b): la existencia de un camino cualquiera de longitud ≤ k de r a s implica la existencia de un camino SIMPLE de longitud ≤ k de r a s. 62. Sea MULTI-MOCHILA el siguiente problema. Demostrar que es NP-completo. Datos: n, M ∈ IN; U1,1 , . . . , U1,M , U2,1 , . . . , Un,M un total de n·M n´ umeros naturales; C1 , . . . , CM ∈ IN. Salida: ¿Existe un conjunto de objetos A ⊆ {1, . . . , n} que cumpla para todo j desde 1 hasta M Si j es impar: Si j es par:

Ui,j ≤ Cj i∈A Ui,j ≥ Cj ?

P

i∈A

P

Codificación de las entradas: sobre el alfabeto Σ = {0, 1, ,}, los n · M + M + 2 n´ umeros naturales que componen una entrada se escriben en binario y se separan por comas. 63. Sea 7-PARTICION el siguiente problema. Demostrar que es NPcompleto. Datos: n ∈ IN el n´ umero de objetos; p1 , p2 , . . . , pn ∈ IN, los pesos de los objetos. Salida: ¿Existen siete conjuntos disjuntos de objetos A1 , . . . , A7 que cumplan para todo k desde 1 hasta 7: X i∈Ak

P

pi =

1≤i≤n

7

pi

?

Codificación de las entradas: sobre el alfabeto Σ = {0, 1, ,}, todos los n´ umeros naturales escritos en binario y separados por comas.


144

64. Sea BOTTLENECK TRAVELING SALESMAN el siguiente problema. Demostrar que es NP-completo. Datos: n, d(1, 1), d(1, 2), . . . , d(n, n), B n´ umeros naturales. Representan n ciudades y d(i, j) es la distancia de la ciudad i a la ciudad j (tales que d(i, j) = d(j, i) y d(i, i) = 0 para todo i, j). Salida: ¿Existe un camino simple C = (c1 , . . . , cn ) (es decir, que pase por todas las ciudades una sola vez) y que cumpla que para todos los i desde 1 hasta n − 1 d(ci , ci+1 ) ≤ B ? Codificación de las entradas: sobre el alfabeto Σ = {0, 1, ,}, todos los n´ umeros naturales escritos en binario y separados por comas. Pista: Relacionarlo con el problema HAM (caminos hamiltonianos sobre grafos no dirigidos). Sólo algunas de las conexiones entre ciudades son “´ utiles”. 65. Sea HAMILTONIAN PATH BETWEEN TWO VERTICES el siguiente problema. Demostrar que es NP-completo. Datos: G un grafo NO DIRIGIDO de vértices V = {1, . . . , n} y aristas A = {a1 , . . . , ak }; r, s ∈ V , dos vértices de G. Salida: ¿Existe un camino hamiltoniano de G (es decir, sin vértices repetidos y que pase por todos los vértices) que empiece en el vértice r y acabe en el vértice s? Codificación de las entradas: sobre el alfabeto Σ = {0, 1, ,}, si u ∈ {0, 1}∗ es n escrito en binario, v ∈ {0, 1}∗ es la matriz de adyacencia de G escrita por filas, y x, y ∈ {0, 1}∗ son r y s en binario, entonces la codificación de la entrada G, r, s es la palabra u, v, x, y. Pista: Relacionarlo con el problema HAM (caminos hamiltonianos sobre grafos no dirigidos). La reducción utilizada a˜ nade 2 vértices nuevos a cada grafo que son principio y final de cualquier camino hamiltoniano.


145

66. Sea X el problema que se enuncia a continuación. Demostrar que X es NP-completo. Datos: n, p1 , p2 , . . . , pn , P, k ∈ IN Salida: ¿Existen A1 , . . . , Ak subconjuntos que cumplan: A1 ∪ . . . ∪ Ak = {1, . . . , n} k X

3

 X 

s=1

pr  ≤ P ?

r∈As

Codificación de las entradas: sobre el alfabeto Σ = {0, 1, ,}, cada n´ umero natural escrito en binario y separados por comas. Pista: Relacionarlo con el problema PARTICION. 67. Sea MAYOR-SUBGRAFO el siguiente problema. Demostrar que es NP-completo. Datos: G grafo NO DIRIGIDO de vértices V = {1, . . . , n} y aristas A, G2 grafo no dirigido de vértices V2 = {1, . . . , r} (r ≤ n) y aristas A2 , k ∈ IN (k ≤ n2 ). Salida: ¿Existe un subconjunto X de k aristas de G2 (es decir, X ⊆ A2 , con #X = k) tal que H = (V2 , X) es un subgrafo de G? Codificación de las entradas: sobre el alfabeto Σ = {0, 1, ,}, si u ∈ {0, 1}∗ es la matriz de adyacencia de G escrita por filas, v ∈ {0, 1}∗ es la matriz de adyacencia de G2 escrita por filas, y w ∈ {0, 1}∗ es k en binario entonces la codificación de la entrada G, G2 , k es la palabra u, v, w. Pista: Relacionarlo con el problema CLIQUE. Nota: H = (V2 , X) es un subgrafo de G = (V, A) si existe V 0 ⊆ V y f : V2 → V 0 biyectiva tal que para cada u, v ∈ V2 , {u, v} ∈ X si y sólo si {f (u), f (v)} ∈ A.


146

68. Sea LONGEST-PATH el siguiente problema. Demostrar que es NPcompleto. Datos: G un grafo DIRIGIDO de vértices V = {1, . . . , n} y aristas A⊆V ×V k ∈ IN, tal que k ≤ n. Salida: ¿Existe un camino simple (es decir, sin vértices repetidos) de G que empiece en el vértice 1 y tenga longitud k? Codificación de las entradas: sobre el alfabeto Σ = {0, 1, , , ; }. Si v ∈ {0, 1, , , ; }∗ es la codificación mediante LISTAS DE ADYACENCIA de G, y w ∈ {0, 1}∗ es k en binario entonces la codificación de la entrada G, k es la palabra v, w 69.

a. Sea FSAT el mismo problema que SAT pero restringido a fórmulas en las que cada variable aparece como máximo 2 veces. Demostrar que FSAT está en P. Pista: Podemos transformas las entradas en fórmulas equivalentes en que cada variable aparezca exactamente dos veces, una afirmada y otra negada, y en cláusulas distintas, y además todas las cláusulas tengan al menos dos literales (hay que justificarlo). Una vez hecho eso, hay un método para ir asignando valores a las variables (¿cuál?). b. Sea 3-PARTICION el siguiente problema. Demostrar que es NP-dif´ıcil. Datos: n ∈ IN el n´ umero de objetos; p1 , p2 , . . . , pn ∈ IN, los pesos de los objetos. Salida: ¿Existe un conjunto de objetos A ⊆ {1, . . . , n} que cumpla X X i∈A

pi =

1≤i≤n

3

pi ?

Codificación de las entradas: sobre el alfabeto Σ = {0, 1, ,}, los n+1 numeros naturales que componen una entrada n, p1 , . . . , pn se escriben en binario y se separan por comas.


147

70. Sea X el problema que se enuncia a continuación. Demostrar que X es NP-completo. Datos: n, p1 , p2 , . . . , pn , P, k ∈ IN Salida: ¿Existen A1 , . . . , Ak subconjuntos de {1, . . . , n} que cumplan: A1 ∪ . . . ∪ Ak = {1, . . . , n} k X

2

 X 

s=1

pr  ≤ P ?

r∈As

Codificación de las entradas: sobre el alfabeto {0, 1, ,}, cada n´ umero natural escrito en binario y separados por comas. Ayuda Relacionarlo con el problema PARTICION. 71. Sea 2-SAT el problema que se enuncia a continuación. Demostrar que 2-SAT está en P. Datos: X, F , donde X es un conjunto de variables, y F una fórmula booleana en forma normal conjuntiva (es decir, escrita como conjunción de cláusulas), y cada cláusula tiene exactamente 2 literales. Salida: ¿Existe una asignación de X que hace cierta F ? Codificación de las entradas: como las entradas de SAT. Ayuda Para hacer cierta una fórmula F : a. Si una variable sólo aparece afirmada (o sólo negada) en F es conveniente asignarle un valor (¿cuál?). b. Si una cláusula es de la forma y ∨ ¬y es siempre cierta. Si una cláusula es de la forma y ∨ y (ó de la forma ¬y ∨ ¬y), hay que asignar a y un valor (¿cuál?). c. Si tenemos varias cláusuals de la forma: (l1 ∨ ¬l2 ), (l2 ∨ ¬l3 ), . . . , (lm−1 ∨ ¬lm ), (lm ∨ ¬l1 )


148

con l1 , . . . , lm literales distintos (y con variables distintas), entonces para hacerlas todas ciertas hay que dar el mismo valor a todos los l1 , . . . , lm , luego podemos sustituir l2 , . . . , lm por l1 en toda F . d. Si tenemos varias cláusuals de la forma: (l1 ∨ ¬l2 ), (l2 ∨ ¬l3 ), . . . , (lm−1 ∨ ¬lm ), (lm ∨ l1 ) con l1 , . . . , lm literales distintos (y con variables distintas), entonces para hacerlas todas ciertas hay que dar un valor a l1 (¿cuál?). 72. Para cada uno de los problemas que se enuncian a continuación, responder a las siguientes preguntas: ¿Está en P? ¿Está en NP? ¿Está en EXP? Las respuestas posibles son tres: S´ı, No y No se sabe, porque es NP-completo. Se puede utilizar que el problema clásico dCLIQUE es NP-completo (as´ı como cualquiera de los otros problemas NP-completos vistos en clase). a. Datos: G un grafo dirigido de vértices V = {1, . . . , n} y aristas A ⊆ V × V ; k ∈ IN, tal que k ≤ n; r ∈ IN, tal que r ≤ n. Salida: ¿Existen V1 , . . . , Vr subconjuntos de V que cumplan 1), 2) y 3)? 1) para todo i 6= j (1 ≤ i, j ≤ r), Vi ∩ Vj = ∅, 2) V1 ∪ . . . ∪ Vr = V , 3) para todo i desde 1 hasta r, el subgrafo de G formado por los vértices Vi tiene un subgrafo completo de al menos k vértices. Codificación de las entradas: sobre el alfabeto Σ = {0, 1, ,}, si u ∈ {0, 1}∗ es n escrito en binario, v ∈ {0, 1}∗ es la matriz de adyacencia de G escrita por filas, w ∈ {0, 1}∗ es k en binario, y z ∈ {0, 1}∗ es r en binario entonces la codificación de la entrada G, k, r es la palabra u, v, w, z.


149

b. Datos: G un grafo dirigido de vértices V = {1, . . . , n} y aristas A ⊆ V × V ; a, b ∈ V ; k ∈ IN, tal que k ≤ n. Salida: ¿Existe un camino del vértice a al vértice b de longitud menor o igual que k? Codificación de las entradas: sobre el alfabeto Σ = {0, 1, ,}, si u ∈ {0, 1}∗ es n escrito en binario, v ∈ {0, 1}∗ es la matriz de adyacencia de G escrita por filas, y x, y, w ∈ {0, 1}∗ son a, b y k en binario, entonces la codificación de la entrada G, a, b, k es la palabra u, v, x, y, w. 73. Para el problema que se enuncia a continuación, responder a las siguientes preguntas: ¿Está en P? ¿Está en NP? ¿Está en EXP? Las respuestas posibles son tres: S´ı, No y No se sabe, porque es NP-completo. Datos: G un grafo dirigido de vértices V = {1, . . . , n} y aristas A⊆V ×V; k ∈ IN, tal que k ≤ n. Salida: ¿Existe un camino de longitud mayor o igual que k que no pase dos veces por un mismo vértice? Codificación de las entradas: sobre el alfabeto Σ = {0, 1, ,}, si u ∈ {0, 1}∗ es n escrito en binario, v ∈ {0, 1}∗ es la matriz de adyacencia de G escrita por filas, y w ∈ {0, 1}∗ es k en binario, entonces la codificación de la entrada G, k es la palabra u, v, w. Pista para 3.: comparar con el problema clásico de existencia de un circuito hamiltoniano (dHAM). 74. Para cada uno de los siguientes problemas, responder a las tres preguntas siguientes: ¿Está en P? ¿Está en NP? ¿Está en EXP? Las respuestas posibles son tres: S´ı, No y No se sabe, porque es NP-completo. a. (Este problema es una variación del clásico PARTICION.) Datos: n ∈ IN el n´ umero de objetos;


150

p1 , p2 , . . . , pn ∈ IN, los pesos de los objetos. Salida: ¿Existen dos conjuntos de objetos A1 , A2 que cumplan las tres condiciones siguientes?: 1) A1 ∪ A2 = {1, . . . , n}. 2) Para todo i, j entre 1 y n, si i ∈ A1 y j ∈ A2 , entonces i< j. X X 3) pi = pi . i∈A1

i∈A2

Codificación de las entradas: sobre el alfabeto Σ = {0, 1, ,}, los n+1 numeros naturales que componen una entrada n, p1 , . . . , pn se escriben en binario y se separan por comas. b. Datos: G = (V, A) un grafo dirigido con V = {1, . . . , n} y aristas A ⊆ V × V ; k ∈ IN, tal que k ≤ n; r ∈ IN, tal que r ≤ n. Salida: ¿Existen V1 , . . . , Vr subconjuntos de V que cumplan 1) y 2)? 1) V1 ∪ . . . ∪ Vr = V , 2) para todo i desde 1 hasta r, el subgrafo de G formado por los vértices Vi tiene un cubrimiento de k vértices como máximo. Codificación de las entradas: sobre el alfabeto Σ = {0, 1, ,}, si u ∈ {0, 1}∗ es n escrito en binario, v ∈ {0, 1}∗ es la matriz de adyacencia de G escrita por filas, w ∈ {0, 1}∗ es k en binario, y z ∈ {0, 1}∗ es r en binario entonces la codificación de la entrada G, k, r es la palabra u, v, w, z. Pista para 3. b): comparar con el problema Vertex Cover.

Índice general 0. Presentaci´ on

1

1. Preliminares. Numerabilidad y ... 1.1. Preliminares . . . . . . . . . . . . . . 1.1.1. Notación lógica: proposiciones 1.1.2. Notación lógica: predicados . 1.1.3. Demostraciones . . . . . . . . 1.1.4. Notación de conjuntos . . . . 1.1.5. Lenguajes . . . . . . . . . . . 1.1.6. Funciones . . . . . . . . . . . 1.2. Numerabilidad . . . . . . . . . . . . 1.3. Diagonalización . . . . . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

4 4 4 5 7 7 8 9 11 16

2. Problemas y datos. Un modelo ... 2.1. Problemas, lenguajes y funciones . . . . . . . . . . 2.1.1. Problemas decisionales y funcionales . . . . 2.1.2. Representación de datos, tama˜ no . . . . . . 2.1.3. Lenguajes y funciones . . . . . . . . . . . . 2.2. La máquina de registros ó Random Access Machine 2.2.1. Codificación de programas . . . . . . . . . . 2.2.2. Notación para programas . . . . . . . . . . . 2.2.3. Más sobre programas . . . . . . . . . . . . . 2.3. Definición de función calculable . . . . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

21 21 21 22 24 25 27 27 28 30

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

3. Problemas decidibles y semidecidibles 32 3.1. Definición y primeros ejemplos de conjunto decidible . . 32 3.2. El problema de parada . . . . . . . . . . . . . . . . . . . 34 151

ÍNDICE GENERAL

152

3.3. Definición y primeros ejemplos de conjunto semidecidible 3.4. Caracterizaciones . . . . . . . . . . . . . . . . . . . . . . 3.5. Propiedades elementales de los conjuntos decidibles y semidecidibles . . . . . . . . . . . . . . . . . . . . . . . . .

35 37 41

4. Reducciones. El teorema de Rice 49 4.1. Reducciones . . . . . . . . . . . . . . . . . . . . . . . . . 49 4.2. Propiedades elementales de las reducciones . . . . . . . . 51 4.3. Conjuntos de ´ındices, teorema de Rice . . . . . . . . . . 56 5. Otros problemas indecidibles

62

6. Otros modelos de c´ alculo: la tesis de ... 6.1. Las funciones recursivas de Gödel y Kleene 6.2. Las máquinas de Turing . . . . . . . . . . 6.3. El λ-cálculo de Church . . . . . . . . . . . 6.4. La tesis de Turing-Church . . . . . . . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

63 64 68 70 73

7. Complejidad y codificaci´ on 7.1. El problema del viajante . . . . . . 7.2. Complejidad en tiempo . . . . . . . 7.3. Cómo codificamos las entradas . . . 7.4. Transformación de cotas de tiempo

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

75 75 77 77 80

. . . .

. . . .

. . . .

. . . .

8. Tiempo polin´ omico versus tiempo ... 82 8.1. Definiciones . . . . . . . . . . . . . . . . . . . . . . . . . 82 8.2. Problemas resolubles en la práctica . . . . . . . . . . . . 84 8.3. Tesis extendida de Turing-Church . . . . . . . . . . . . . 86 9. Estudio de algunos problemas ... 9.1. SAT . . . . . . . . . . . . . . . 9.2. MOCHILA . . . . . . . . . . . 9.3. CLIQUE . . . . . . . . . . . . . 9.4. La clase NP . . . . . . . . . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

90 90 94 96 98

10.Reducciones en tiempo polin´ omico 103 10.1. Definición . . . . . . . . . . . . . . . . . . . . . . . . . . 103 10.2. Primer ejemplo . . . . . . . . . . . . . . . . . . . . . . . 104

ÍNDICE GENERAL

153

10.3. Propiedades elementales . . . . . . . . . . . . . . . . . . 106 11.Los problemas NP-completos 11.1. El concepto de NP-completo . . . . . 11.2. Una reducción complicada . . . . . . 11.3. Algunos problemas NP-completos . . 11.3.1. El problema del Vertex Cover 11.3.2. El problema PARTICION . . 11.3.3. Siete NP-completos . . . . . .

. . . . . .

110 110 112 117 117 119 120

12.Ejercicios de examen 12.1. Teor´ıa . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12.2. Problemas de computabilidad . . . . . . . . . . . . . . . 12.3. Problemas de complejidad . . . . . . . . . . . . . . . . .

123 123 130 137

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

Modelos Abstractos 13d19

Overview 1s532p

More details 6h715l

Related Documents 2w1qw

Modelos Abstractos 13d19

Rostros Abstractos 5t723m

Inventos Abstractos Y Concretos 1p644u

Sustantivos Concretos Y Abstractos 2t4030

10 Ejemplos De Sustantivos Abstractos 1p4a2o

Poemas Abstractos Y Escritos Recopilados f5r27

More Documents from "Lizbeth Sol" 1i2z6o

Modelos Abstractos 13d19

504uu

Premise Indirect 2010 3k4h6m

Lerner Y Sadovsky El Sistema Numeracion Problema Didactico.pdf 6n6j66

Importancias De Las Cuentas 4h566r

Carbohydrate - Wikipedia 30231v