1. No category

1
Curso Básico de Computación
12 Teorı́a de la Complejidad
Computacional
Hasta ahora se ha visto como la teorı́a de lenguajes clasifica los conjuntos por
su complejidad estructural. Otra clasificación, llamada complejidad computacional, está basada en la cantidad de tiempo, espacio, u otros recursos utilizados para reconocer un lenguaje en alguna máquina de cómputo universal, tal
como la máquina de Turing.
12.1 Definiciones
Complejidad en espacio
c|
Entrada
$
Control
finito
Cintas de almacenamiento
Considérese la máquina de Turing M de la figura anterior. M tiene una cinta
de sólo–lectura con marcadores en los extremos c| y $, y k cintas de almacenamiento semi–infinitas. Si por cada palabra de entrada de longitud n, M lee
a lo sumo S(n) celdas en cualquiera de las cintas de almacenamiento, entonces
se dice que M es una máquina de Turing espacio–acotada S(n), o de complejidad en espacio S(n). El lenguaje reconocido por M se dice también que es
de complejidad en espacio S(n).
Obsérvese que no se puede reescribir en la entrada de M , y que solamente
Feliú Sagols Troncoso
Matemáticas-Cinvestav
2
interesa la longitud de las cintas de almacenamiento. Esta restricción permite
considerar acotamientos de crecimiento inferiores al lineal. Si la MT pudiera
reescribir en la cinta de entrada, entonces la longitud de la entrada tendrı́a
que ser incluida en calcular el acotamiento en espacio, por lo que no podrı́a
ser inferior al lineal.
Complejidad en Tiempo
Control
finito
Región de
entrada
Cintas de almacenamiento
La MT de la figura anterior tiene k cintas infinitas de doble vı́a, una de las
cuales contiene la entrada. Se puede escribir en todas las cintas, incluyendo
la de la entrada. Si para cada palabra de entrada de longitud n, M realiza a
lo más T (n) movimientos antes de detenerse, entonces se dice que M es una
máquina de Turing tiempo–acotada, o de complejidad en tiempo T (n).
Ejemplo Considérese el lenguaje
L = {wcw R |w ∈ (0 + 1)∗ }.
El lenguaje L es de complejidad en tiempo n + 1, debido a que existe una
máquina de Turing M1 , con dos cintas, que copia la entrada a la izquierda del
c en la segunda cinta. Luego, cuando una c es encontrada, M1 mueve la cabeza
de lectura de su segunda cinta a la izquierda, leyendo la cadena que acaba de
copiar, y de manera simultánea continúa moviendo su cabeza de lectura de la
cinta de entrada hacia la derecha. De esa manera se comparan los sı́mbolos
mientras ambas cabezas se mueven a la vez. Si los signos comparados son los
3
Curso Básico de Computación
mismos, y la cardinalidad de la palabra antes del sı́mbolo c coincide con la
cardinalidad de la palabra a su derecha, entonces la cadena es aceptada por
M1 . Es fácil observar que M1 realiza a lo más n + 1 movimientos si la entrada
es de longitud n.
Existe otra máquina de Turing, M2 , de complejidad en espacio log2 n que
acepta a L. M2 utiliza dos cintas de almacenamiento para contadores binarios. Primero, se revisa que la entrada contenga solamente una c, y que el
número de sı́mbolos a la izquierda de c coincida con el número de sı́mbolos
a su derecha. Luego, las palabras a la derecha e izquierda son comparadas
sı́mbolo por sı́mbolo, utilizando los contadores para encontrar los sı́mbolos
correspondientes. Si no concuerdan, M2 se detiene sin aceptar. Si todos los
sı́mbolos coinciden, entonces M2 acepta la cadena.
Suposiciones especiales acerca de las
funciones de complejidad en espacio y
tiempo
Debe ser obvio que cada MT utiliza por lo menos una celda para cualquier
entrada, por lo que si S(n) es una medida de complejidad en espacio, se puede
asumir S(n) ≥ 1 para cualquier n. Ası́, una suposición importante al hablar
de la “complejidad en espacio S(n)”, es que nos referimos al max(1, dS(n)e).
De manera similar, se asume que cualquier complejidad en tiempo T (n) es
al menos n + 1, pues es el tiempo que se necesita para leer la entrada y verificar que se ha alcanzado el final cuando se lea el primer espacio en blanco. Ası́,
por convención, “complejidad en tiempo T (n)” significa max(n + 1, dT (n)e).
Complejidades en tiempo y espacio no
determinı́sticas
Una MT no determinı́stica es de complejidad en tiempo T (n) si cualquier secuencia de movimientos causa que la máquina realice a lo más T (n) movimientos. Es de complejidad en espacio S(n) si cualquier secuencia la obliga a leer
a lo sumo S(n) celdas en cualquier cinta de almacenamiento.
Clases de complejidad
La familia de lenguajes de complejidad en espacio S(n) se denota por DSPACE(S(n));
los lenguajes de complejidad no determinı́stica S(n) se llaman de manera colectiva NSPACE(S(n)). La familia de lenguajes de complejidad en tiempo T (n)
se denota por DTIME(T (n)) y los de complejidad no determinı́stica en tiempo
por NTIME(T (n)). Todas estas familias de lenguajes son llamadas clases de
complejidad.
Feliú Sagols Troncoso
Matemáticas-Cinvestav
4
12.2 Aceleración lineal, compresión
lineal de cintas y reducciones lineales
en el número de cintas
Compresión de cintas
Teorema 12.1 Si L es aceptado por una máquina de Turing espacio–acotada
S(n) con k cintas de almacenamiento, entonces para cualquier c > 0, L es
aceptado por una MT espacio-acotada cS(n).
Demostración Sea M1 una máquina de Turing fuera de lı́nea espacio–acotada
S(n) que acepta a L. La prueba consiste en construir una nueva máquina de
Turing M2 que simule M1 , donde para alguna constante r, cada celda de la
cinta de almacenamiento de M2 contenga un sı́mbolo representando los contenidos de r celdas adyacentes de la cinta correspondiente de M1 . El control
finito de M2 puede mantener información sobre cuál de las celdas de M1 , entre
aquellas representadas, está en realidad leyendo M1 .
Sea r tal que rc ≥ 2. M2 puede simular M1 utilizando a lo sumo dS(n)/re
celdas en cualquier cinta. Si S(n) ≥ r, este número no es mayor a cS(n).
Si S(n) < r, entonces M2 puede almacenar en una celda los contenidos de
cualquier cinta. Ası́, M2 utiliza solamente una celda en el último caso.
Corolario Si L está en NSPACE(S(n)), entonces L está en NSPACE(cS(n)),
donde c es cualquier constante mayor que cero.
Demostración Si la M1 anterior es no determinı́stica, sea M2 no determinı́stica
en la construcción anterior.
Reducción en el número de cintas para
las clases de complejidad en espacio
Teorema 12.2 Si un lenguaje L es aceptado por una MT espacio–acotada
S(n) con k cintas de almacenamiento, es aceptado por una MT espacio–
acotada S(n) con una única cinta de almacenamiento.
Demostración Sea M1 una MT espacio–acotada S(n) con k cintas de almacenamiento que acepta a L. Se puede construir una nueva máquina de Turing
M2 con una única cinta de almacenamiento, la cual simule las cintas de almacenamiento de M1 con k pistas. La técnica se utilizó en el teorema 7.2. M2
utiliza no más de S(n) celdas.
Desde ahora se asume que cualquier MT espacio–acotada S(n) tiene únicamente
una cinta de almacenamiento, y si S(n) ≥ n, entonces es una MT de cinta
única, en lugar de una MT fuera de lı́nea con una cinta de almacenamiento y
una cinta de entrada.
5
Curso Básico de Computación
Aceleración lineal
Dada una función f (n), la expresión supn→∞ f (n) se define como el lı́mite
cuando n → ∞ de la menor cota superior de f (n), f (n + 1), f (n + 2), . . . De
manera similar, inf n→∞ f (n) es el lı́mite cuando n → ∞ de la mayor cota
inferior de f (n), f (n + 1), f (n + 2), . . . . Si f (n) converge a un lı́mite cuando
n → ∞, entonces ese lı́mite es igual tanto al inf n→∞ f (n) como al supn→∞ f (n).
Ejemplo Sea f (n) = 1/n para n par, y f (n) = n para n impar. Ası́ el
supn→∞ f (n) = ∞, mientras que el inf n→∞ f (n) = 0.
En otro ejemplo, sea f (n) = n/(n + 1). Ası́, supn→∞ f (n) = inf n→∞ f (n) = 1.
Teorema 12.3 Si L es aceptado por una máquina de Turing tiempo–acotada
T (n) con k–cintas M1 , entonces L es aceptado por una MT tiempo–acotada
cT (n) con k–cintas M2 para cualquier c > 0, siempre que k > 1 y inf n→∞ T (n)/n =
∞.
Demostración Una MT M2 puede ser construida de manera que simule M1
de la siguiente manera. Primero, M2 copia la entrada en una cinta de almacenamiento, codificando m sı́mbolos en uno (el valor de m será determinado
luego). A partir de este punto, M2 utiliza su cinta de almacenamiento como
la cinta de lectura, y utiliza la cinta de lectura anterior como cinta de almacenamiento. M2 codificará los contenidos de las cintas de almacenamiento de M1
combinando m sı́mbolos en uno. Durante el desarrollo de la simulación, M2
simula un mayor número de movimientos de M1 en un paso básico que consiste
de ocho movimientos de M2 . Se nombran a las celdas que están siendo leı́das
por cada una de las cabezas de M2 celdas hogar. El control finito de M2 graba,
para cada cinta, cuál de los m sı́mbolos de M1 representados por cada celda
hogar está siendo leı́do por la correspondiente cabeza de M2 .
Para comenzar el paso básico, M2 mueve cada cabeza a la izquierda una vez, a
la derecha dos veces y a la izquierda una, grabando los sı́mbolos de la izquierda
y la derecha de las celdas hogar en su control finito. Se requieren cuatro
movimientos de M2 , después de los cuales M2 regresa a sus celdas hogar.
Luego, M2 determina los contenidos de todas las celdas de las cintas de M1 representadas por las celdas hogar y sus vecinos a izquierda y derecha al momento
en el que alguna cabeza de M1 abandonde primero la región representada por la
celda hogar y sus vecinos a izquierda y derecha (note que este cálculo no toma
tiempo en M2 . Se construye en las reglas de transición de M2 ). Si M1 acepta
antes de que alguna cabeza abandone la región representada, M2 acepta. Si
M1 se detiene, M2 se detiene. Si no ocurriera eso, entonces M2 visita, en
cada cinta, los dos vecinos de la celda hogar, cambiando estos sı́mbolos y el
de la celda hogar si fuera necesario. M2 coloca cada una de sus cabezas en
la celda que representa el sı́mbolo que la cabeza correspondiente de M1 está
Feliú Sagols Troncoso
Matemáticas-Cinvestav
6
leyendo al final de los movimientos simulados. A lo sumo se necesitan cuatro
movimientos de M2 .
Se necesitan por lo menos m movimientos de M1 para mover la cabeza fuera de
la región representada por una celda hogar y sus vecinos. Ası́, en 8 movimientos, M2 ha simulado por lo menos m movimientos de M1 . Se escoge m de tal
manera que cm ≥ 16.
Si M1 realiza T (n) movimientos, entonces M2 los simula en a lo sumo 8dT (n)/me
movimientos. También, M2 debe copiar y codificar su entrada (m celdas en
una), luego regresar la cabeza de la cinta de entrada simulada al extremo
izquierdo. Esto toma n + dn/me movimientos, para un total de
n + dn/me + 8dT (n)/me
(12.1)
movimientos. Como dxe < x + 1 para cualquier x, (12.1) está acotada superiormente por
n + n/m + 8T (n)/m + 2.
(12.2)
Ahora se asume que inf n→∞ T (n)/n = ∞, por lo que para cualquier constante
d existe un nd tal que para toda n ≥ nd , T (n)/n ≥ d, o expresado de otra
manera, n ≤ T (n)/d. Ası́, siempre que n ≥ 2 (lo que implica que n + 2 ≤ 2n)
y n ≥ nd , (12.2) está acotada superiormente por
8
2
1
T (n)
+ +
.
(12.3)
m d md
Todavı́a no se ha especificado a d. Recordando el hecho de que cm ≥ 16,
se escoge d = m/4 + 81 , y se sustituye m por 16/c en (12.3). Entonces para
toda n ≥ max(2, nd ), el número de movimientos realizados por M2 no excede
a cT (n).
Para reconocer el número finito de palabras de longitud menor que el máximo
de 2 y nd , M2 utiliza únicamente su control finito, tomando n + 1 movimientos
para leer su entrada y alcanzar la celda en blanco que marca el final de la
entrada. Ası́ el tiempo de complejidad de M2 es cT (n). Recuerde que por
complejidad en tiempo, cT (n) se refiere al max(n + 1, dcT (n)e).
Corolario Si inf n→∞ T (n)/n = ∞ y c > 0, entonces
DTIME(T (n)) = DTIME(cT (n)).
Demostración El teorema 12.3 es una prueba directa para cualquier lenguaje
L aceptado por una MTD con dos o más cintas en tiempo T (n). Claramente
si L es aceptado por una MT de 1-cinta, es aceptado por una MT de 2-cintas
de la misma complejidad en tiempo.
El teorema 12.3 no se aplica si T (n) es un múltiplo constante de n, puesto que
7
Curso Básico de Computación
entonces inf n→∞ T (n)/n es una constante, no infinito. Sin embargo, la construcción del Teorema 12.3, con un análisis más cuidadoso en la cota de tiempo
de M2 , muestra lo siguiente.
Teorema 12.4 Si L es aceptado por una MT tiempo–acotada cn de k–cintas,
para k > 1 y para alguna constante c, entonces para cada > 0, L es aceptado
por una MT tiempo–acotada (1 + )n de k-cintas.
Demostración Tómese m = 16 · c/ en la demostración del teorema 12.3.
Corolario Si T (n) = cn para alguna c > 1, entonces DTIME(T (n)) =
DTIME((1 + )n) para cualquier > 0.
Corolario (de los teoremas 12.3 y 12.4)
a. Si inf n→∞ T (n)/n = ∞, entonces NTIME(T (n)) = NTIME(cT (n)) para
cualquier c > 0.
b. Si T (n) = cn para alguna constante c, entonces NTIME(T (n)) = NTIME((1+
)n), para cualquier > 0
Demostración Las pruebas son análogas a los teoremas 12.3 y 12.4
Reducción en el número de cintas para
las clases de complejidad en tiempo
Teorema 12.5 Si L está en DTIME(T (n)), entonces L es aceptado en tiempo
T 2 (n) por una MT de una cinta.
Demostración En la construcción del teorema 7.2, donde se pasaba de una
MT multicintas a una MT de una sola cinta, M2 utiliza a lo sumo 6T 2 (n)
pasos para simular T (n) pasos de M√
1 . Por el teorema 12.3, se puede acelerar
M1 para que corra en tiempo T (n)/ 6. Entonces M2 es una MT de una sola
cinta que acepta a L en T 2 (n) pasos.
Corolario Si L está en NTIME(T (n)), entonces L es aceptado por una MTND
de una sola cinta de tiempo en complejidad no determinı́stico T 2 (n).
Demostración Análoga a la prueba del teorema.
Si se restringe a dos cintas la pérdida de tiempo es considerablemente menor.
Teorema 12.6 Si L es aceptado por una máquina de Turing con k–cintas
tiempo–acotada T (n), entonces L es aceptado por una MT M2 , la cual consiste
de dos cintas de almacenamiento, en tiempo T (n) log T (n).
Feliú Sagols Troncoso
Matemáticas-Cinvestav
8
Demostración La primera cinta de almacenamiento de M2 tendrá dos pistas
por cada cinta de almacenamiento de M1 . Por conveniencia, nos enfocaremos
en dos pistas correspondientes a una cinta en particular de M1 . Las otras cintas de M1 se simulan exactamente de la misma manera. La segunda cinta de
M2 es un almacenador temporal, pues se utiliza únicamente para transportar
bloques de datos en la cinta 1.
Una celda en particular de la cinta 1, conocida como B0 , tendrá los sı́mbolos de
almacenamiento leı́dos por cada una de las cabezas de M1 . En lugar de mover
los marcadores de las cabezas, M2 transportará datos a través de B0 en la
dirección opuesta a la del movimiento de la cabeza de M1 que está siendo simulada. Ası́ M2 puede simular cada movimiento de M1 por mirar únicamente a
B0 . A la derecha de la celda B0 estarán los bloques B1 , B2 , . . . de longitud exponencialmente creciente; es decir, con Bi de longitud 2i−1 . Similarmemente,
a la izquierda de B0 existen bloques B−1 , B−2 , . . . con B−i de longitud 2i−1 .
Se asume que existen marcadores entre los bloques, a pesar de que ellos no
aparecen hasta que el bloque es utilizado.
a0 va a denotar los contenidos de la celda inicialmente escaneada por la cabeza
de lectura de la cinta de M1 . Los contenidos de las celdas a la derecha de ésta
son a1 , a2 , . . . , y los de su izquierda a−1 , a−2 , . . . Los valores de las ai ’s pueden
cambiar cuando entren a B0 ; no son sus valores, sino sus posiciones en las
pistas de la cinta 1 de M2 lo que importa. Inicialmente se asume que la pista
superior de M2 para la cinta de M1 en cuestión, está vacı́a, mientras que la
pista inferior tiene . . . , a−2 , a−1 , a0 , a1 , a2 , . . . Estos se colocan en los bloques
. . . , B−2 , B−1 , B0 , B1 , B2 , . . . como se muestra en la siguiente figura.
a−7 a−6 a−5 a−4 a−3 a−2 a−1
|
{z
B−3
} | {z }
B−2
a0
B−1 B0
a1
B1
a2
a3
a4
| {z } |
B2
a5
a6
{z
B3
a7
}
Después de la simulación de cada movimiento de M1 , ocurrirá lo siguiente:
1) Para cualquier i > 0, o Bi está llena (ambas pistas) y B−i está vacı́a, o
Bi está vacı́a y B−i está llena, o tanto las pistas inferiores de Bi y B−i están
llenas mientras que las pistas superiores están vacı́as.
2) Los contenidos de Bi (o de B−i ) representan celdas consecutivas en la cinta
representada de M1 . Para i > 0, la pista superior representa celdas a la
izquierda de aquellas representadas por la pista inferior; para i < 0, la pista
9
Curso Básico de Computación
superior representa a celdas que están a la derecha de aquellas que están en la
pista inferior.
3) Para i < j, Bi representa celdas a la izquierda de aquellas de Bj .
4) B0 tiene llena únicamente su pista inferior, y su pista superior está marcada
de manera especial.
Para mostrar cómo es que los datos son transferidos, se puede imaginar que
la cabeza de la cinta de M1 en cuestión se mueve a la izquierda. Entonces M2
debe de mover el dato correspondiente a la derecha. Para hacerlo, M2 mueve
la cabeza de la cinta 1 desde B0 , donde descansa, y se va hacia la derecha
hasta que encuentra el primer bloque, digamos Bi , que no tiene llenas ambas
pistas. Entonces M2 copia todos los datos de B0 , B1 , . . . , Bi−1 , en la cinta 2
y los almacena en la pista inferior de B1 , B2 , . . . , Bi−1 más la pista inferior
de Bi , asumiendo que la pista inferior de Bi no está llena aún. En caso de
que ya estuviera llena, se utiliza entonces la pista superior. En cualquiera
de los dos casos, hay espacio suficiente para distribuir los datos. Nótese que
los datos pueden ser tomados y almacenados en su nueva locación en tiempo
proporcional a la longitud de Bi .
Luego, en tiempo proporcional a la longitud de Bi , T1 puede encontrar B−i
(por ejemplo, utilizando la cinta 2 para medir la distancia desde Bi hasta B0 ).
Si B−i está completamente llena, T1 toma la pista superior de B−i y la almacena en la cinta 2. Si B−i está medio llena, la pista inferior se pone en la cinta
2. En cualquier caso, lo que ha sido copiado en la cinta 2 es luego copiado a las
pistas inferiores de B−(i−1) , B−(i−2) , . . . , B0 (por la regla 1, estas pistas tienen
que estar vacı́as, puesto que las de B1 , B2 , . . . , Bi−1 estaban llenas. Nuevamente, obsérvese que hay suficiente espacio para almacenar los datos, y todas
las operaciones anteriores pueden realizarse en tiempo proporcional a la longitud de Bi . También se puede observar que los datos pueden ser distribuidos
de manera que satisfagan las reglas (1), (2) y (3).
Se da el nombre a todo lo que se acaba de describir de operación-Bi . El caso
en el cual la cabeza de M1 se mueve a la derecha es análogo. En la siguiente
figura se muestra el contenido sucesivo de los bloques conforme M1 mueve su
cabeza por 5 celdas hacia la izquierda.
Feliú Sagols Troncoso
B−3
Matemáticas-Cinvestav 10
B−2
B−1 B0 B1
a−7 a−6 a−5 a−4 a−3 a−2 a−1 a0
a1
B2
B3
a2
a3
a4
a5
a6
a7
a2
a3
a4
a5
a6
a7
a0
a1
a−3 a−2 a−1 a2
a3
a4
a5
a6
a7
a−2 a0
a1
a−3 a−1 a2
a3
a4
a5
a6
a7
a0
a1
a2
a3
a−7 a−6 a−5 a−4 a−3 a−2 a−1 a4
a5
a6
a7
a0
a1
a2
a3
a−5 a−3 a−2 a−1 a4
a5
a6
a7
a0
a−7 a−6 a−5 a−4 a−3 a−2
a−7 a−6 a−5 a−4
a−1 a1
a−7 a−6 a−5 a−4
a−4
a−7 a−6
Se puede observar que por cada cinta de M1 , M2 debe realizar una operaciónBi a lo sumo una vez por cada 2i−1 movimientos de M1 , pues necesita esta
cantidad de movimientos por B1 , B2 , . . . , Bi−1 , los cuales están semivacı́os después de una operación-Bi , para llenarla. También, una operación-Bi no puede
ser realizada hasta que hayan ocurrido al menos 2i−1 movimientos en M1 . De
aquı́, si M1 opera en tiempo T (n), M2 realizará únicamente operaciones-Bi ,
para aquellas i tales que i ≤ log2 T (n) + 1.
Hasta ahora se puede concluir que existe una constante m, tal que M2 utiliza a
lo sumo m2i movimientos para realizar una operación-Bi . Si M1 realiza T (n)
movimientos, M2 realiza a lo sumo
log2 T (n)+1
T1 (n) =
X
i=1
m2i
T (n)
2i−1
(12.4)
movimientos cuando simula una cinta de M1 .
De (12.4), se obtiene
T1 (n) = 2mT (n)dlog2 T (n) + 1e,
y de (12.5),
T1 (n) < 4mT (n) log2 T (n).
(12.5)
11
Curso Básico de Computación
El lector debe ser capaz de observar que M2 opera en tiempo porporcional a
T1 (n) incluso cuando M1 realiza movimientos utilizando diferentes cintas de
almacenamiento en lugar de solamente la única en la cual se ha concentrado la
demostración. Por el teorema 12.3, se puede modificar M2 para que se ejecute
en no más de T (n) log2 T (n) pasos.
Corolario Si L es aceptado por una MTND de k-cintas de complejidad en
tiempo T (n), entonces L es aceptado por una MTND de dos cintas de complejidad en tiempo T (n) log T (n).
Demostración Análoga a la demostración del teorema.
12.3 Teoremas de jerarquı́a
Teorema 12.7 Dada cualquier cota en tiempo (cota en espacio) totalmente
recursiva T (n), existe un lenguaje recursivo L que no está en DTIME(T (n))
(o en DSPACE(T (n)) respectivamente).
Demostración Se demostrará el resultado para el tiempo; el argumento para el
espacio es análogo. El argumento es básicamente una diagonalización. Debido
a que T (n) es totalmente recursiva, existe una MT M para T (n) que siempre
se detiene. Se construye M̂ para que acepte un lenguaje L ⊆ (0 + 1)∗ que es
recursivo pero no está en DTIME(T (n)). Sea xi la i-ésima cadena en el orden
canónico de (0+1)∗ . En el capı́tulo 8, se ordenaron MT’s de una sola cinta con
el alfabeto {0, 1, B}. De manera similar se pueden ordenar MT’s multicinta
con alfabetos de cintas arbitrarios reemplazando sus funciones de transición
por cadenas binarias. El único punto substancial es que los nombres de los
sı́mbolos de las cintas, ası́ como aquellos de los estados, no importan, ası́ que
se puede asumir que todas las MT cuyo alfabeto de entrada es {0, 1} tienen
alfabetos de cintas 0, 1, B, X4 , X5 , . . . , Xm , ası́ se codifica 0, 1 y B por 0, 00 y
000, y se codifica Xi por 0i , i ≥ 4. También se permite un número arbitrario
de unos en frente del código para M que represente también a M , ası́ que M
tiene codificaciones arbitrariamente largas.
Ası́ se puede hablar libremente de Mi , la i-ésima MT multicinta. Ahora se define L = {xi |Mi no acepta a xi dentro de T (|xi |) movimientos}. Se afirma que
L es recursivo. Para reconocer a L se puede ejecutar el siguiente algoritmo,
el cual puede ser implementado en una MT. Dada la entrada w de longitud
n, se simula n en M para computar T (n). Entonces se determina i tal que
w = xi . El entero i escrito en binario es la función de transición de alguna
MT multicinta Mi (si i en binario es una forma impropia para una función de
transición, entonces Mi no tiene movimientos). Se simula w en Mi para T (n)
movimientos, aceptando tanto si Mi se detiene sin aceptarlo o si Mi se ejecuta
por más de T (n) movimientos sin haber aceptado.
Para observar que L no está en DTIME(T (n)), supóngase que L = L(Mi ), y
Feliú Sagols Troncoso
Matemáticas-Cinvestav 12
Mi es acotado en tiempo T (n). ‘?Está xi en L? Si es ası́, Mi acepta a xi
dentro de T (n) movimientos, donde n = |xi |. Ası́, por definición de L, xi no
está en L, lo cual es una contradicción. Si xi no está en L, entonces Mi no
acepta a xi , ası́ que por la definición de L, xi está en L, lo cual es nuevamente
una contradicción. Ambas suposiciones conllevan a contradicciones, ası́ que la
suposición de que Mi es acotada en tiempo T (n) debe ser falsa.
Si T 0 (n) ≥ T (n) para todo n, se sigue de manera inmediata de la definición de
una clase de complejidad en tiempo que DTIME(T (n)) ⊆ DTIME(T 0 (n)). Si
T (n) es una función totalmente recursiva, el teorema 12.7 implica que existe
un conjunto recursivo L que no está en DTIME(T (n)). Sea T̂ (n) el tiempo de
corrida de alguna MT que acepta a L y sea T 0 (n) = max{T (n), T̂ (n)}. Entonces DTIME(T (n)) ( DTIME(T 0 (n)), puesto que L está en el último pero
no en el primero de ellos. Ası́ se sabe que existe una jerarquı́a infinita de clases
de complejidad en tiempo determinı́sticas. Un resultado similar se aplica para
las clases de complejidad en espacio determinı́sticas y para las clases en tiempo
y espacio no determinı́sticas.
El teorema 12.7 demuestra que para cualquier complejidad recursiva en tiempo
o espacio f (n), existe una f 0 (n) tal que algún lenguaje se encuentra en la clase
de complejidad definida por f 0 (n) pero no por f (n).
Una jerarquı́a en espacio
Una función S(n) se dice que es construible en espacio si existe alguna máquina
de Turing M tal que es acotada en espacio S(n), y para cada n, existe alguna
entrada de longitud n en la cual M utiliza S(n) celdas de la cinta. El conjunto de funciones construibles en espacio incluye log n, nk , 2n y n!. Si S1 (n) y
S2 (n) son construibles en espacio, entonces también lo son S1 (n)S2 (n), 2S1 (n) y
S1 (n)S2 (n) . Ası́ el conjunto de funciones construibles en espacio es muy extenso.
Observe que la MT M arriba mencionada no necesita utilizar una cantidad
de espacio S(n) en todas las entradas de longitud n, solamente en alguna entrada de esa longitud. Si para toda n, M utilizara exactamente S(n) celdas en
cualquier entrada de longitud n, entonces se dice que S(n) es completamente
construible en espacio. Cualquier función construible en espacio S(n) ≥ n es
completamente construible en espacio (ejercicio).
Con el fin de simplificar el siguiente resultado se demuestra el lema:
Lema 12.1 Si L es aceptada por una MT espacio–acotada S(n) ≥ log 2 n,
entonces L es aceptada por una MT espacio–acotada S(n) que se detiene en
todas sus entradas.
Demostración Sea M una máquina de Turing fuera de lı́nea espacio–acotada
S(n) con s estados y t sı́mbolos en la cinta que acepta a L. Si M acepta, lo
13
Curso Básico de Computación
hace por una secuencia de a lo más (n + 2)sS(n)tS(n) movimientos, puesto que
si no, de otra manera, alguna DI se repetirı́a. Es decir, existen n + 2 posiciones de la cabeza de entrada, s estados, S(n) posiciones de la cabeza de la
cinta, y tS(n) contenidos en la cinta de almacenamiento. Si se agrega una pista
adicional como un contador de movimientos, M puede detenerse por sı́ misma
después de (4st)S(n) ≥ (n + 2)sS(n)tS(n) movimientos. De manera más exacta,
se coloca en M un contador de longitud log n que cuenta en base 4st. Siempre
que M lee una nueva celda que está más allá de las celdas que contienen el
contador, M incrementa la longitud del contador. Ası́ si M se cicla habiendo
utilizado solamente i celdas de la cinta, entonces el contador detectará esto
cuando la cuenta alcance (4st)max(i,log2 n) , lo cual es al menos (n + 2)sS(n)tS(n) .
Teorema 12.8 Si S2 (n) es una función completamente espacio–construible,
S1 (n)
= 0,
n→∞ S2 (n)
inf
y además S1 (n) y S2 (n) son cada una al menos log2 n, entonces existe un
lenguaje en DSPACE(S2 (n)) que no está en DSPACE(S1 (n)).
Demostración El teorema se demuestra por diagonalización. Considérese una
enumeración de máquinas de Turing fuera de lı́nea con alfabeto de entrada
{0, 1} y con una cinta de almacenamiento, basada en la codificación binaria
de la sección 8.3, pero permitiendo un prefijo de 1’s, para que cada MT tenga
codificaciones arbitrariamente largas. Se construye una MT M que utiliza
espacio S2 (n) y no concuerda con al menos una entrada con cualquier MT
espacio–acotada S1 (n).
Con la entrada w, M comienza por marcar S2 (n) celdas en una cinta, donde
n es la longitud de w. Puesto que S2 (n) es completamente construible en espacio, esto puede ser hecho simulando una MT que utiliza exactamente S2 (n)
celdas en cada entrada de longitud n. En lo que sigue, si M intenta abandonar
las celdas marcadas, M se detiene y rechaza a w. Esto garantiza que M sea
acotada en espacio S2 (n).
Lo siguiente es que M comienza una simulación en la MT Mw (la MT codificada por la cadena binaria w) de la entrada w. Si Mw está acotada en espacio
S1 (n) y tiene t sı́mbolos en la cinta, entonces la simulación requiere espacio
dlog2 teS1 (n). M acepta a w solamente si M puede completar la simulación
en espacio S2 (n) y Mw se detiene sin aceptar a x.
Debido a que M está acotada en espacio S2 (n), L(M ) está en DSPACE(S2 (n)).
L(M ) no está en DSPACE(S1 (n)). Supóngase que existe una MT M̂ espacio–
acotada S1 (n) con t sı́mbolos en la cinta que acepta L(M ). Por el lema 12.1 se
puede asumir que M̂ se detiene en todas las entradas. Puesto que M̂ aparece
Feliú Sagols Troncoso
Matemáticas-Cinvestav 14
infinitamente seguido en la enumeración, y
inf
n→∞
S1 (n)
= 0,
S2 (n)
existe una cadena w lo suficientemente larga, |w| = n, tal que dlog 2 teS1 (n) <
S2 (n) y Mw es M̂ . Con la entrada w, M tiene el espacio suficiente para simular
Mw y aceptar si y solo si Mw rechaza. De donde L(Mw ) 6= L(M ), lo cual es una
contradicción. Ası́ L(M ) está en DSPACE(S2 (n)) pero no en DSPACE(S1 (n)).
Mientras que la mayorı́a de las funciones son completamente construibles en el
espacio, se necesita únicamente constructibilidad en el espacio para el teorema
12.8.
Corolario El teorema 12.8 es cierto incluso si S2 (n) es construible en espacio pero no completamente construible en espacio.
Demostración Sea M1 una MT que construye S2 (n) en alguna entrada. Sea Σ
el alfabeto de la entrada de M1 . Se diseñará M para que acepte un lenguaje
sobre el alfabeto Σ × {0, 1}. Eso es, la entrada a M es tratada como si tuviera
dos pistas: la primera es utilizada como la entrada de M1 , la segunda como el
código de una MT con alfabeto de entrada Σ × {0, 1}. La única modificación
al diseño de M es que M debe marcar bloques en las cintas 1 y 2 simulando
M1 en la primera pista de M . Se debe demostrar que M no concuerda con
ninguna MT M̂ tiempo–acotada S1 (n) en una entrada cuya longitud, n, sea
suficientemente larga, cuya primera pista es una cadena en Σn que cause que
M1 utilice S2 (n) celdas, y cuya segunda pista es una codificación de M̂ .
Se deja como ejercicio la demostración de que la condición S2 (n) ≥ log2 n en
el teorema 12.8 y su corolario no es necesaria. La demostración no es una
diagonalización, sino que se basa en mostrar que
{wci w|w ∈ (a + b)∗ ,
|w| = S2 (n) y i = n − 2S2 (n)}
es aceptada en espacio S2 (n) pero no en espacio S1 (n) si
inf
n→∞
S1 (n)
= 0,
S2 (n)
y S2 (n) < log2 n.
Nótese que si inf n→∞ [S1 (n)/S2 (n)] = 0 y S1 (n) ≤ S2 (n) para toda n, entonces
DSPACE(S1 (n)) ( DSPACE(S2 (n)).
Sin embargo, si no se tiene que S1 (n) ≤ S2 (n), entonces es posible que
DSPACE(S1 (n)) y DSPACE(S2 (n)) contengan lenguajes no incluidos en el
otro.
15
Curso Básico de Computación
Una jerarquı́a en tiempo
Se dice que una función T (n) es construible en tiempo si existe una máquina
de Turing multicinta M tiempo–acotada T (n) tal que por cada n existe alguna entrada en la cual M realiza exactamente T (n) movimientos. Igual que
las funciones espacio–construibles, existe una extensa jerarquı́a de funciones
tiempo–construibles. Se dice que T (n) es completamente construible en tiempo
si existe una MT que utiliza tiempo T (n) en todas las entradas de longitud
n. Nuevamente, la mayorı́a de las funciones comunes son completamente construibles en tiempo.
Teorema 12.9 Si T2 (n) es una función completamente tiempo–construible,
y
T1 (n) log T1 (n)
= 0,
inf
n→∞
T2 (n)
entones existe un lenguaje en DTIME(T2 (n)) pero no en DTIME(T1 (n)).
Demostración La demostración es similar a la del teorema 12.8, y solamente
se presenta una breve explicación de la construcción necesaria. Una MT M
tiempo–acotada T2 (n) se construye para operar de la manera siguiente. M
trata la entrada w como una codificiación de una máquina de Turing M̂ y
simula w en M̂ . Una dificultad surge debido a que M tiene un número fijo
de cintas, ası́ que para algunas w’s, M̂ tendrá más cintas que M . Afortunadamente, por el teorema 12.6, se necesitan únicamente dos cintas para simular cualquier M̂ , a pesar que está simulación tiene como costo un factor de
log T1 (n). Además, debido a que M̂ puede tener muchos sı́mbolos de cinta, los
cuales deben ser codificados en un número fijo de sı́mbolos, la simulación de
T1 (n) movimientos de M̂ por M requiere tiempo cT1 (n) log T1 (n), donde c es
una constante que depende de M̂ .
Con el fin de asegurar que la simulación de M̂ esté acotada en tiempo T2 (n),
M ejecuta de manera simultánea los pasos de una MT (utilizando cintas adicionales) que utilicen exactamente un tiempo T2 (n) en todas las entradas de
longitud n. Esta es la razón por la cual T2 (n) debe ser completamente construible en tiempo. Después de T2 (n) pasos, M se detiene. M acepta a w
solamente si la simulación de M̂ se completa y M̂ rechaza a w. La codificación de M̂ está diseñada como en el teorema previo, para que ası́ M̂ tenga
codificaciones arbitrariamente largas. Ası́, si M̂ es una máquina de Turing
tiempo–acotada T1 (n), existirá una w lo suficientemente larga que codifique a
M̂ de tal manera que
cT1 (|w|) log T1 (|w|) ≤ T2 (|w|),
y la simulación llegará a un final. En este caso, w está en L(M ) si y solamente
si w no está en L(M̂ ). Ası́ L(M ) 6= L(M̂ ) para cualquier M̂ que sea acotada
en tiempo T1 (n). Por lo tanto L(M ) está en DTIME(T2 (n)) − DTIME(T1 (n)).
Feliú Sagols Troncoso
Matemáticas-Cinvestav 16
Ejemplo Sea T1 (n) = 2n y T2 (n) = n2 2n . Entonces
T1 (n) log2 T1 (n)
1
= inf
= 0.
n→∞
n→∞ n
T2 (n)
inf
Ası́ se puede utilizar el teorema 12.9, y DTIME(2n ) 6= DTIME(n2 2n ). Puesto
que T1 (n) ≤ T2 (n) para toda n, se puede concluir que DTIME(2n ) ( DTIME(n2 2n ).