Complejidad

computacional
PID_00267022

Joaquim Borges
Robert Clarisó
Ramon Masià
Jaume Pujol
Josep Rifà
Joan Vancells
Mercè Villanueva

Tiempo mínimo de dedicación recomendado: 4 horas

CC-BY-NC-ND • PID_00267022 Complejidad computacional

Joaquim Borges Robert Clarisó Ramon Masià

Jaume Pujol Josep Rifà Joan Vancells

Mercè Villanueva

El encargo y la creación de este recurso de aprendizaje UOC han sido coordinados

por el profesor: Robert Clarisó (2019)

Cuarta edición: septiembre 2019

Autoría: Joaquim Borges, Robert Clarisó, Ramon Masià, Jaume Pujol, Josep Rifà, Joan Vancells, Mercè
Villanueva
Licencia CC BY-NC-ND de esta edición, FUOC, 2019
Av. Tibidabo, 39-43, 08035 Barcelona
Realización editorial: FUOC

Los textos e imágenes publicados en esta obra están sujetos –excepto que se indique lo contrario– a una licencia de
Reconocimiento-NoComercial-SinObraDerivada (BY-NC-ND) v.3.0 España de Creative Commons. Podéis copiarlos, distribuirlos
y transmitirlos públicamente siempre que citéis el autor y la fuente (FUOC. Fundación para la Universitat Oberta de Catalunya),
no hagáis de ellos un uso comercial y ni obra derivada. La licencia completa se puede consultar en [Link]
licenses/by-nc-nd/3.0/es/[Link]
CC-BY-NC-ND • PID_00267022 Complejidad computacional

Índice general

Introducción . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

1. Concepto de problema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.1. Problemas decisionales, de cálculo y de optimización . . . . . . . . . 8
Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
Soluciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.2. Algunos problemas decisionales importantes . . . . . . . . . . . . . . . . . 11
1.2.1. Satisfactibilidad de fórmulas booleanas . . . . . . . . . . . . . . . 12
1.2.2. Partición de conjuntos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
Soluciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

2. Medidas de complejidad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.1. Tiempo y espacio . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.1.1. El tamaño de la entrada . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
Soluciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.2. Las clases de complejidad P y EXP . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.3. La clase de complejidad NP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
Soluciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
?
2.4. Jerarquía de complejidad y la cuestión P = NP . . . . . . . . . . . . . . . . 26
Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
Soluciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

3. Reducciones y completitud . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
3.1. El concepto de reducción polinómica . . . . . . . . . . . . . . . . . . . . . . . . . 30
Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
Soluciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
3.2. Propiedades de las reducciones, transitividad
y equivalencia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
Soluciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
3.3. Completitud . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
CC-BY-NC-ND • PID_00267022 Complejidad computacional

Soluciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

Ejercicios de autoevaluación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

Solucionario . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

Bibliografía . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
CC-BY-NC-ND • PID_00267022 5 Complejidad computacional

Introducción

Este módulo es una introducción a la Teoría de la Complejidad Computacio-

nal. Esta rama de la Informática Teórica estudia cuáles son los límites prácticos
de cálculo de los ordenadores.

Ante un problema, el objetivo será medir su dificultad inherente: la cantidad

de recursos computacionales (tiempo de ejecución y espacio de memoria) que
necesita un ordenador para calcular su solución. Esta complejidad temporal y
espacial se estudia en términos del tamaño de los datos de entrada.

A grandes rasgos, queremos distinguir entre aquellos problemas donde el pro-

ceso de resolución es escalable incluso para grandes volúmenes de datos (pro-
blemas tratables) de aquellos donde el consumo de recursos se dispara rápida-
mente hasta llegar a ser prohibitivo (problemas intratables). Por ejemplo, ¡en
problemas intratables es frecuente hablar de tiempos de ejecución superiores
a la vida del universo! Se trata, pues, de problemas que nunca se podrán re-
solver en la práctica por mucho que avance la capacidad de cálculo de los
ordenadores.

En este módulo, formalizaremos el concepto de problema y las técnicas pa-

ra medir su complejidad computacional. Presentaremos diversos ejemplos de
problemas “famosos” de diferentes ámbitos de la Informática, caracterizando
su complejidad.

Además, para facilitar su clasificación, definiremos varias clases de problemas

de una complejidad equivalente y estudiaremos las relaciones entre las clases.
Por último, introduciremos una técnica llamada reducción que permite com-
parar la complejidad de dos problemas diferentes. De esta manera, ante un
problema nuevo seremos capaces de establecer a qué clase pertenece y decidir
si es “igual de complejo” o “más complejo” que otros problemas conocidos.
CC-BY-NC-ND • PID_00267022 7 Complejidad computacional

1. Concepto de problema
.

El punto de partida de la Teoría de la Complejidad es el concepto de problema

que se puede resolver con un ordenador.

Definición 1

Un problema computacional es un enunciado donde, partiendo de

una información de entrada (instancia), se pide una respuesta finita
(solución) con unas características determinadas.

Formalmente, un problema Prob es una función Prob : I → S de un con-

junto de instancias I a un conjunto de soluciones S . Prob(x) denotará
la solución al problema Prob con entrada x.

x∈I→ Prob → Prob(x) ∈ S

Ejemplo 1

RC: “Dado un número real no negativo x, calcular su raíz cuadrada.”

Este problema
√ corresponde a una función RC : R+ → R+ , concretamente la función
RC(x) = x. Por ejemplo, tendremos que RC(4) = 2 y RC(5) = 2,2360679.

Ejemplo 2 Secuencia

BUSQUEDA_ORD: “Dada una secuencia finita de enteros E ordenada en orden creciente Una secuencia es una serie de
y un entero k, decidir si el número k aparece en la secuencia.” elementos donde el orden de
los elementos es relevante y
En este caso, cada entrada del problema es un par de valores (una secuencia y un en- puede haber repeticiones: h i,
tero), mientras que la solución es sencillamente SÍ o NO. Formalmente, podríamos de- h3, – 1i, h4,4,15, – 2,5,6i, . . .
finir la función BUSQUEDA_ORD :
Z∗ × Z → {SÍ,NO}. Así, tendríamos por ejemplo
que BUSQUEDA_ORD h–2,3,45,50i,3
= SÍ mientras que con otra entrada tenemos que
BUSQUEDA_ORD h5,11,29i,24 = NO. Notación

Dado un conjunto C,
A lo largo de este módulo, veremos muchos ejemplos de problemas compu- llamaremos C∗ al conjunto
de todas las secuencias finitas
tacionales. Algunos de ellos son muy relevantes por sus aplicaciones prácticas
de elementos de C,
y, por lo tanto, es interesante recordarlos y aprender a reconocerlos. Clasifi- incluyendo la secuencia vacía
h i.
caremos el grado de dificultad de estos problemas a partir del análisis de los
algoritmos que calculan su solución.
CC-BY-NC-ND • PID_00267022 8 Complejidad computacional

1.1. Problemas decisionales, de cálculo y de optimización

Empezaremos la clasificación de los problemas computacionales distinguien-

do diferentes categorías según la solución esperada.

Definición 2

Un problema Prob : I → S es un problema decisional o de decisión si

el conjunto de soluciones S es {SÍ,NO}. Dicho de otra forma, el proble-
ma consiste en establecer si la entrada satisface una cierta propiedad.

SÍ
ր
x∈I→ DECISIÓN
ց
NO

Ejemplo 3

PAR: “Dado un número natural n, determinar si es par.”

Este problema es una función PAR : N → {SÍ,NO}. Por ejemplo, PAR(16) = SÍ y PAR(7) =
NO.

Ejemplo 4

CONEXO: “Dado un grafo G = (V,A), determinar si es conexo.”

Si llamamos G al conjunto de todos los grafos, podemos definir este problema como la
función CONEXO : G → {SÍ,NO}. Por ejemplo, para los grafos completos Kn tendríamos
que CONEXO(Kn ) = SÍ para cualquier valor de n.

Definición 3

Dado un problema decisional Prob : I → {SÍ, NO}, denotamos por Prob•

el conjunto de las entradas que tienen solución SÍ.

Prob• = {x ∈ I | Prob(x) = SÍ}

Utilizando esta notación de conjuntos, la notación x ∈ Prob• es equiva-

lente a Prob(x) = SÍ y x 6∈ Prob• es equivalente a Prob(x) = NO.
CC-BY-NC-ND • PID_00267022 9 Complejidad computacional

Ejemplo 5

Podemos definir el problema PAR• como el conjunto {0,2,4,6,8,10, . . .}. Podemos expre-
sar que PAR(8) = SÍ como 8 ∈ PAR• y que PAR(11) = NO como 11 6∈ PAR• .

Ejemplo 6

Llamaremos ProbSI a un problema decisional que tiene solución SÍ para cualquier en-
trada. Evidentemente, el conjunto ProbSI• = I, ya que todas las entradas pertenecen a
ProbSI• . En cambio, si un problema tiene solución NO para cualquier entrada se llama
ProbNO y está claro que ProbNO• = ∅. ProbSI y ProbNO nos serán útiles para obtener
algunos resultados teóricos a lo largo de este módulo.

Definición 4

Un problema Prob : I → S es un problema de cálculo si el conjunto de

soluciones S es diferente de {SÍ, NO}. En estos problemas, la solución
es un valor (un número, un conjunto, un grafo, . . . ) que se tiene que
calcular a partir de la entrada de acuerdo con el enunciado del proble-
ma.

x∈I→ CÁLCULO → Valor ∈ S

Ejemplo 7

SUMATORIO: “Dada una secuencia finita de enteros E, obtener su suma total.”

Este problema se puede describir como SUMATORIO : Z∗ → Z. Es un problema de

cálculo, ya que la solución es un número entero (S = Z). Tendríamos por ejemplo que
SUMATORIO(h22, – 35, – 18,47,16i) = 32.

Ejemplo 8 Notación

AISLADOS: “Dado un grafo G = (V,A), determinar el conjunto de vértices de grado cero Si C es un conjunto, 2C
(aislados).” representa el conjunto
formado por todos los
El problema AISLADOS : G → 2V es de cálculo porque tiene como solución un subcon- subconjuntos de C.
junto de los vértices V del grafo que no tienen ninguna arista incidente. Por ejemplo,
para los grafos completos Kn tenemos que AISLADOS(Kn ) = ∅ para cualquier n. En cam-
bio, en los grafos nulos Nn todos los vértices son aislados, es decir, AISLADOS(Nn ) = V.
CC-BY-NC-ND • PID_00267022 10 Complejidad computacional

Definición 5

Un problema Prob : I → S es un problema de optimización si es un

problema de cálculo (S =
6 {SÍ, NO}) y la solución tiene que ser óptima
(mínima o máxima) de acuerdo con una función de valoración definida
en el enunciado del problema. Dicho de otra manera, en un problema
de optimización se pide la mejor solución según un cierto criterio.

x∈I → OPTIMIZACIÓN → Óptimo(S )

Ejemplo 9

CPP: “Dado un conjunto de puntos en un espacio bidimensional, donde cada punto está
definido por las coordenades (x,y), calcular el par de puntos que son más próximos entre Nomenclatura
sí.”
En inglés, este problema se
Este problema puede verse como una función CPP : 2R×R → (R × R) × (R × R). Un ejem- llama closest pair problem.

solución sería
la que se muestra a continuación: CPP {(0,10),(5,20),(–2,0),(30, –
plo de
50)} = (0,10),(–2,0) .

El problema CPP es un problema de optimización. La función de valoración que se está

optimizando es la distancia entre el par de puntos de la solución. En este caso, el objetivo
es minimizar esta función.

Ejemplo 10

LCS: “Dadas dos cadenas de caracteres a y b, encontrar la subcadena común más larga
entre a y b.” Nomenclatura

Si Σ es el alfabeto de símbolos sobre el que hemos definido las cadenas de caracteres, En inglés, este problema se
podemos describir LCS como la función LCS : Σ∗ × Σ∗ → Σ∗ . Un ejemplo de solución llama longest common
sería LCS(“andromeda”, “dromedary”) = “dromeda”. substring.

LCS es un problema de optimización donde la función de valoración a optimizar es la

longitud de la cadena común. El objetivo es maximizar esta función.

Ejemplo 11

MSP: “Dado un grafo conexo y ponderado, es decir, un grafo G = (V,A) y la función de

ponderación w, calcular un árbol generador minimal.” Nomenclatura

Este problema tiene como entrada un grafo G = (V,A) y una función de ponderación, y En inglés, este problema se
como solución un grafo. Es decir, podemos describirlo como la función MSP : G × (A → llama minimum spanning tree.
R) → G. La función de valoración en este caso es el peso del árbol generador, que se
pretende minimizar.

Ejercicios

1. Definid los siguientes problemas en forma de función y clasificadlos como problemas de

decisión, cálculo u optimización:
a) Dado un grafo conexo y ponderado (G,w) con G = (V,A), y dos vértices a,b ∈ V, determinar
el camino más corto entre a y b.
CC-BY-NC-ND • PID_00267022 11 Complejidad computacional

b) Dada una secuencia finita de enteros E y un valor k, contar el número de apariciones de k

dentro de E.

c) Dado un grafo G, comprobar si es un grafo completo.

d) Dado un grafo G, encontrar el subgrafo completo de orden máximo.

e) Dada una cadena de caracteres c, indicar si contiene todos los dígitos del 0 al 9.

2. Justificad si son ciertas o falsas las afirmaciones siguientes (repasad el ejemplo 5):
a) Si un grafo G es un árbol, entonces G 6∈ CONEXO• .

b) Si x 6∈ PAR• , entonces 2 · x ∈ PAR• .

Soluciones

1. a) Prob : G × (A → R) × V × V → A∗ . Problema de optimización. La función de valoración

es el peso del camino y se desea minimizarlo.

b) Prob : Z∗ × Z → Z. Problema de cálculo.

c) Prob : G → {SÍ,NO}. Problema de decisión.

d) Prob : G → G. Problema de optimización. La función de valoración es el orden (número

de vértices) del subgrafo completo y se desea maximizarlo.

e) Prob : Σ∗ → {SÍ,NO}. Problema de decisión.

2. a) Falsa. Por definición, todos los árboles son grafos conexos y por lo tanto CONEXO(G) =
SÍ. Para ser correcta, la afirmación debería decir G ∈ CONEXO• .

b) Cierta. Aunque un número sea impar (PAR(x) = NO), el doble de cualquier número siem-
pre será par (PAR(2x) = SÍ).

1.2. Algunos problemas decisionales importantes

En el resto del módulo, nos centraremos únicamente en los problemas deci-

sionales. El motivo de esta elección aparentemente tan restrictiva es que cual-
quier problema de cálculo o de optimización se puede reformular en versión
decisional:

Tipo Enunciado original Versión decisional

Cálculo “Dada una entrada x, calcular el “Dada una entrada x y un valor k,
valor de salida f (x)” decidir si f (x) = k”
Optimización “Dada una entrada x, calcular el “Dada una entrada x y un valor lí-
valor de salida f (x) que maximiza mite l, decidir si hay alguna salida
el criterio c” f (x) tal que c(f (x)) ≥ l”

Podemos ver que la versión decisional es “más sencilla” que el problema origi-
nal de cálculo o optimización: el algoritmo que resuelve el problema original
puede solucionar también la versión decisional. Así pues, si demostramos que
la versió decisional es “difícil”, tendremos que las versiones de cálculo y op-
timización también lo son. Es decir, estudiar la complejidad de los problemas
CC-BY-NC-ND • PID_00267022 12 Complejidad computacional

decisionales nos da información sobre la complejidad de los problemas de

cálculo y optimización asociados. Pero fijémonos en que sólo tenemos infor-
mación en un sentido: si la versión decisional de un problema es “sencilla”,
no sabemos si las versiones de cálculo o de optimización también serán “sen-
cillas” o si serán “difíciles”.

1.2.1. Satisfactibilidad de fórmulas booleanas

Definición 6

Una variable booleana es una variable que puede tomar los valores de
verdad 0 (falso) o 1 (cierto).

Una fórmula booleana es una combinación de variables mediante ope-

raciones lógicas como la conjunción y-lógica (∧), la disyunción o-lógica
(∨) o la negación no (x).

Un literal es una variable booleana (x) o su negación (x).

Una cláusula es una disyunción (o-lógica) de literales (x1 ∨ . . . ∨ xn ).

Una fórmula está en forma normal conjuntiva (FNC) si es una con-

junción (y-lógica) de cláusulas: (x1 ∨ . . . ∨ xn1 ) ∧ . . . ∧ (y1 ∨ . . . ∨ ynk ).

Ejemplo 12

La fórmula booleana siguiente sobre las variables a, b y c

(a ∧ b ∧ c) ∨ (a ∧ c) ∨ b

contiene 5 literales sin negar y uno negado (b). Podemos ver que no está en FNC: no
es la conjunción de cláusulas, sino una disyunción de conjunciones. Para estar en FNC
debería tener una forma como

(a ∨ b ∨ c) ∧ (a ∨ c) ∧ b.

Esta última fórmula tiene 3 cláusulas: una de 3 literales, una de 2 y una de 1 literal. Si se
evalúa la fórmula, por ejemplo, para a = 1, b = 1 y c = 0 el resultado es 1 y para a = 0, b =
1 y c = 0 el resultado es 0.
CC-BY-NC-ND • PID_00267022 13 Complejidad computacional

Problema de decisión 7

SAT (satisfactibilidad): Dada una fórmula booleana f : V → {0,1} en

FNC, decidir si hay alguna asignación de valores de verdad a las varia-
bles V que satisface f (es decir, hace que f evalúe a 1).

Si cada cláusula de f tiene exactamente 3 literales, estamos ante un caso

particular de SAT llamado el problema de la 3-satisfactibilidad (3SAT).

Ejemplo 13

Dada la fórmula f = (a ∨ b) ∧ (a ∨ c), tenemos que SAT(f ) = SÍ. De hecho, de las 23 asig-
naciones de valores de verdad a las variables {a,b,c}, hay 5 asignaciones que satisfacen la
fórmula:

a b c
0 0 0
0 0 1
0 1 0
0 1 1
1 1 0

En cambio, ninguna de las 24 = 16 asignaciones de valores de verdad satisface la fórmula

siguiente:

(a ∨ b ∨ c) ∧ (a ∨ c) ∧ b ∧ (a ∨ c) ∧ (a ∨ d) ∧ (c).

Comprobémoslo: las cláusulas b y c nos obligan a que b = 1 y c = 0; las cláusulas (a ∨

c) y (a ∨ c) nos obligan a que a = 1; pero entonces, la primera cláusula no se puede
satisfacer. Como f es una conjunción de cláusulas, si la primera cláusula no se puede
satisfacer entonces f es insatisfactible.

Se podría pensar que el problema SAT sólo tiene sentido en el contexto de

la lógica o el diseño de circuitos digitales, pero es una impresión errónea.
Cualquier problema sobre un dominio acotado se puede codificar mediante
variables y fórmulas booleanas. En otras palabras, muchos problemas reales se
pueden expresar como instancias de SAT.

Ejemplo 14

Tres profesores (Pilar, Ricardo y María) tienen que vigilar tres exámenes (1, 2 y 3). Cada
examen debe tener al menos un vigilante, aunque también puede tener más de uno.
A Ricardo no le va bién el horario del primer examen, y el segundo y el tercero están
solapados y se tienen que asignar a personas diferentes. Finalmente, cada profesor debe
vigilar al menos un examen.

Queremos decidir si hay alguna asignación de vigilancias de examen factible. Este pro-
blema es equivalente a decidir si la fórmula siguiente es satisfactible (pi = 1 indica que
Pilar vigila el examen i-ésimo y similarmente para Ricardo y María).
CC-BY-NC-ND • PID_00267022 14 Complejidad computacional

(r1 ) ∧ (p2 ∨ p3 ) ∧ (r2 ∨ r3 ) ∧ (m2 ∨ m3 ) ∧

(p1 ∨ p2 ∨ p3 ) ∧ (r1 ∨ r2 ∨ r3 ) ∧ (m1 ∨ m2 ∨ m3 )∧
(p1 ∨ m1 ∨ r1 ) ∧ (p2 ∨ m2 ∨ r2 ) ∧ (p3 ∨ m3 ∨ r3 )

Esta fórmula es satisfactible si, por ejemplo, p1 = 1, m2 = 1, r3 = 1 y el resto de variables

están a 0.

1.2.2. Partición de conjuntos

. Multiconjunto

Problema de decisión 8 Un multiconjunto es una

colección no ordenada de
PARTICION: Dado un multiconjunto de enteros C, decidir si existe un elementos donde puede
subconjunto C′ ⊆ C tal que la suma de todos los elementos de C′ sea haber repeticiones. Se
representan entre corchetes,
igual a la suma de los elementos fuera de C′ . por ejemplo, [7,3,7,24]. Un
subconjunto de un
multiconjunto también
 X  puede ser un multiconjunto.
∃C′ ⊆ C |
X
PARTICION(C) ≡ x = y
x ∈ C′ y ∈ C \C ′

Ejemplo 15


Podemos ver que PARTICION [2,3,3,34] = NO. Para justificarlo, tenemos que comprobar
que ninguna partición del conjunto tiene la misma suma. En un multiconjunto con n
elementos, hay como máximo 2n–1 particiones (asumiendo que la mitad de particiones
son simétricas, es decir, que de una partición a la otra sólo se intercambian C′ y C \ C′ ):

C′ Suma de C′ C \ C′ Suma de C \ C′

∅ 0 [2,3,3,34] 42
[2] 2 [3,3,34] 40
[3] 3 [2,3,34] 39
[34] 34 [2,3,3] 8
[2,3] 5 [3,34] 37
[3,3] 6 [2,34] 36

En cambio PARTICION [3,4,12,17,18,22,28] = SÍ, ya que tenemos dos subconjuntos con
suma total 52, [3,4,28,17] y [22,18,12].

El nombre PARTICION proviene de que buscamos partir el multiconjunto en

dos partes con la misma suma total. En la práctica, PARTICION aparece cuando
se quiere repartir equitativamente entre dos entitades un conjunto de tareas
o recursos independientes entre sí. Usualmente, al tratar problemas de pla-
nificación o logística se planteará la versión de optimización del problema
(encontrar el reparto más equitativo).
CC-BY-NC-ND • PID_00267022 15 Complejidad computacional

Ejemplo 16
Nomenclatura
Un notario tiene que dividir un conjunto de obras de arte dejadas en herencia a dos he-
rederos. En primer lugar, necesita decidir si hay algún reparto equitativo. Este problema En inglés, el problema
se puede ver como una instancia de PARTICION, donde el valor monetario de cada obra PARTICION se llama
sería un valor entero dentro del multiconjunto. partition.

Ejemplo 17

Un array de discos debe almacenar una lista de ficheros en dos discos y es necesario de-
cidir dónde se guarda cada fichero. Se desea que la ocupación de cada disco sea lo más
equilibrada posible. Este problema vuelve a ser una instancia de la versión de optimi-
zación de PARTICION, donde el espacio ocupado por cada fichero es un valor entero
dentro del multiconjunto a particionar.

. Nomenclatura

Problema de decisión 9 En inglés, el problema

SUMA_SUB se llama subset
SUMA_SUB (suma de subconjuntos): Dado un conjunto de enteros C y sum.

un entero t, decidir si existe un subconjunto C′ ⊆ C tal que la suma de

todos los elementos de C′ sea igual a t.

 X 
SUMA_SUB(C,t) ≡ ∃C′ ⊆ C : x=t
x ∈ C′

Ejemplo 18


Tenemos que SUMA_SUB {1,9,10,17,20},48 = SÍ, ya
que {1, 10, 17, 20} tiene como suma
total 48. En cambio, SUMA_SUB {1,9,10,17,20},35 = NO, aunque para comprobarlo
deberíamos estudiar los 25 = 32 subconjuntos del conjunto original.

En este problema, t es el objetivo a alcanzar (capacidad a ocupar, beneficio a

conseguir, . . . ) mientras que los valores del conjunto modelan los elementos
a combinar para llegar al objetivo (su coste, tamaño, . . . ).

Ejemplo 19

Queremos comprar un producto de una máquina expendedora que sólo acepta el impor-
te exacto. Para hacerlo, tenemos en nuestra cartera un puñado de monedas. Si todas las
monedas tienen un valor diferente, decidir si podemos comprar el producto es una ins-
tancia de SUMA_SUB, donde C es el conjunto de valores de las monedas y t es el precio
del producto.

Ejercicios

3. Indicad cuáles de las siguientes fórmulas están en FNC:

a ∧ b, a ∨ b, (a ∨ b), (a ∨ b) ∧ b ∧ a, a ∨ (b ∧ c)

4. ¿Hay alguna fórmula booleana en FNC con exactamente dos cláusulas que sea insatisfac-
tible? Y si además esta fórmula tuviera que ser una entrada de 3SAT, ¿cambiaría la respuesta?
CC-BY-NC-ND • PID_00267022 16 Complejidad computacional

5. Indicad cuáles de estas fórmulas booleanas son entradas correctas de 3SAT:

(a ∨ b ∨ c), (a ∨ b ∨ c) ∧ (a ∨ b), (a ∨ c) ∨ (b ∧ c) ∨ (b ∧ c)

6. Indicad si las siguientes fórmulas en FNC son satisfactibles y, si lo son, calculad una asig-
nación de valores de verdad que las satisface:
a) x ∧ (x ∨ y) ∧ z ∧ (x ∨ y ∨ z)

b) (y ∨ z) ∧ (x ∨ z) ∧ (x ∨ y)

7. Dado un multiconjunto de enteros C, demostrad que si PARTICION(C) = SÍ entonces la

suma de todos los elementos de C es un número par.

8. Dadas las siguientes entradas de PARTICION, indicad cuál es su solución. En caso de que
la solución sea SÍ, indicad cuál sería la partición.
a) C1 = [1,2,3,4,5,6,7,8,9,10,11].

b) C2 = [18,175, – 64,14,13].

Soluciones

3. Las fórmulas en FNC son: a ∧ b, a ∨ b y (a ∨ b) ∧ b ∧ a. Respecto a las otras, a ∨ b tiene una

o-lógica dentro de una negación y a ∨ (b ∧ c) es una disyunción de conjunciones.

4. Sí: (a ∧ a). En cambio, si la fórmula es una entrada de 3SAT, todas las fórmulas con 2
cláusulas serán siempre satisfactibles.

5. Sólo (a∨b∨c), ya que tiene 3 literales en todas las cláusulas (en este caso, su única cláusula).
(a ∨ b ∨ c) ∧ (a ∨ b) tiene una cláusula con 2 literales mientras que (a ∨ c) ∨ (b ∧ c) ∨ (b ∧ c) ni
siquiera está en FNC.

6. a) No es satisfactible.

b) Es satisfactible, por ejemplo, para: x = 0, y = 1 y z = 1.

7. Si PARTICION(C) = SÍ, quiere decir que C se puede dividir en dos partes con la misma
suma total. Si llamamos s a la suma de los elementos de cada una de estas partes, la suma de
todos los elementos de C será 2s que es un número par.

8. a) PARTICION(C1 ) = SÍ. Una posible partición sería C′ = [3,9,10,11] y C1 \C′ = [1,2,4,5,6,7,8].

Una estrategia para calcular la partición en esta instancia tan pequeña es calcular prime-
ro la suma total (66) y entonces buscar un conjunto de elementos que sumen en total la
mitad (33).

b) PARTICION(C2 ) = NO. Fijémonos que 175 – 64 es más grande que la suma del resto de
enteros positivos.
CC-BY-NC-ND • PID_00267022 17 Complejidad computacional

2. Medidas de complejidad
.

2.1. Tiempo y espacio

La complejidad computacional de un algoritmo es una métrica abstracta de

la cantidad de recursos necesarios para calcular una solución. Considerare-
mos dos recursos de cálculo diferentes: el tiempo de ejecución y el espacio de
memoria.

Definición 10

El tiempo de ejecución de un algoritmo es una medida del número de

pasos de cálculo o operaciones elementales necesarias para obtener el
resultado.

El espacio de memoria consumido por un algoritmo es una medida

del número de posiciones de memoria (bits) necesarios para almacenar
el resultado final y los cálculos intermedios.

En función del recurso a medir, hablaremos de complejidad temporal o com-

Ved también
plejidad espacial. En ambos casos, no se pretende cuantificar un valor con-
creto (segundos, instrucciones, bits o megabytes) sino la tasa de crecimiento En el módulo, “Conceptos
previos: funciones y
respecto al tamaño de la entrada. Usaremos la notación O para describir es- algoritmos”, podéis repasar la
notación O definida.
ta tasa de crecimiento en el caso peor, es decir, la entrada que consume más
recursos.

Ejemplo 20

Un cuadrado mágico es una matriz n × n de números naturales que contiene los números
del 1 al n2 sin repeticiones y de forma que la suma de cada fila, columna y diagonal
principal es igual al mismo valor. Un ejemplo de cuadrado mágico 3 × 3 es la matriz

8 3 4
1 5 9
6 7 2

Estudiemos la complejidad espacial y temporal de un algoritmo que, dada una matriz

n × n, compruebe si es un cuadrado mágico.

Nuestro algoritmo debe calcular el sumatorio de n filas, n columnas y 2 diagonales prin-

cipales. Cada sumatorio requiere n – 1 sumas. Por lo tanto, nuestro algoritmo tiene que
CC-BY-NC-ND • PID_00267022 18 Complejidad computacional

hacer (2n + 2)(n – 1) sumas. Después es necesario comparar los resultados entre sí, es decir,
es necesario hacer 2n + 1 comparaciones. En resumen, la complejidad temporal es O(n2 ).

Respecto a la complejidad espacial, tenemos que es necesario almacenar el resultado par-

cial del sumatorio a medida que lo vamos calculando (O(1)) y el resultado del sumatorio
previo para hacer la comparación (O(1)). La complejidad espacial del algoritmo es pues
O(1).

La complejidad temporal y la complejidad espacial de un algoritmo no tie-

nen por qué ser iguales, pero sí que deben mantener una cierta relación: la
complejidad temporal siempre será igual o superior a la complejidad espacial.
El motivo es que si se utilizan N posiciones de memoria, el algoritmo deberá
realizar al menos N pasos para leer o escribir sus contenidos. Por lo tanto, la
complejidad temporal es una cota superior de la complejidad espacial.

Para analizar y comparar la complejidad de los algoritmos, agruparemos las

funciones de coste en dos grandes categorías: complejidad polinómica y com-
plejidad exponencial. Intuitivamente, las funciones de coste polinómicas tie-
nen una tasa de crecimiento muy inferior y por lo tanto permiten resolver un
problema para entradas de tamaño grande. En cambio, las funciones de cos-
te exponenciales rápidamente se vuelven inasumibles a medida que crece la
entrada.

Definición 11

Un algoritmo tiene complejidad polinómica (espacial o temporal) si

la tasa de crecimiento de su coste respecto al tamaño de la entrada (n)
es del orden de O(nk ) para alguna constante k.

Un algoritmo tiene complejidad exponencial (espacial o temporal) Aproximación de Stirling

si la tasa de crecimiento de su coste respecto al tamaño de la entrada (n)
k
Para valores grandes de n, el
es del orden de O(2O(n ) ) para alguna constante k.
factorial n! se puede
aproximar
√ por
n! ≈ 2πn( ne )n . Por este
motivo, O(n!) se considera
también un coste
Ejemplo 21
exponencial.

Veamos a continuación algunos ejemplos de complejidades temporales polinómicas y

exponenciales:

Complejidad Nombre Ejemplo de problema

O(1) Constante Determinar si un número es par.
O(log n) Logarítmica Buscar un valor en un vector ordenado.
O(n) Lineal Buscar un valor en un vector desordenado.
O(n log n) Cuasilineal Ordenar un vector (merge-sort).
O(n2 ) Cuadrática Ordenar un vector (bubble-sort).
O(n3 ) Cúbica Calcular el producto de dos matrices.
O(2n ) Exponencial Listar todos los subconjuntos de un conjunto de n elementos.
Listar todas las asignaciones de valores de verdad a n variables booleanas.
O(n!) Factorial Listar todas las permutaciones de n elementos.
CC-BY-NC-ND • PID_00267022 19 Complejidad computacional

Un problema puede tener uno o más algoritmos que calculen su solución.

La complejidad espacial y temporal de un problema se define a partir de es-
tos algoritmos, concretamente la complejidad del algoritmo más eficiente que
calcula la solución.

Definición 12

Una función f es calculable en tiempo polinómico si existe un algo-

ritmo que calcula f (x) en tiempo polinómico para cualquier entrada x.

Un problema Prob es resoluble en tiempo polinómico si Prob(x) es

calculable en tiempo polinómico.

Similarmente, podemos dar las definiciones para la complejidad espa-

cial (substituyendo tiempo por espacio) y para la complejidad exponen-
cial (substituyendo polinómico por exponencial).

Definición 13

Un problema Prob es tratable si es resoluble en tiempo polinómico.

Un problema Prob es intratable si es resoluble en tiempo exponencial

pero no es resoluble en tiempo polinómico.

2.1.1. El tamaño de la entrada

Antes de empezar a estudiar complejidades temporales o espaciales tenemos

que hacer una reflexión sobre el tamaño de la entrada de un algoritmo. En
los módulos anteriores, hemos expresado la complejidad de los algoritmos en
función del tamaño de su entrada. La entrada podía ser un grafo, un conjunto,
una lista, un número entero, . . .

Ejemplo 22

En el análisis de la complejidad de la mayoría de los algoritmos sobre grafos (Dijkstra,

Floyd, . . . ) la entrada es un grafo G = (V,A), y analizamos la complejidad en términos del
orden (el número n de vértices) del grafo y su medida (el número m de aristas).

En los algoritmos de ordenación, la entrada está formada por una lista o secuencia de
números enteros y la complejidad se calcula en función de la longitud (número n de
elementos) de la lista.

En el algoritmo de multiplicar y elevar, la entrada está formada por un número x y un

exponente entero y positivo N. La complejidad se calcula en función del valor de N.
CC-BY-NC-ND • PID_00267022 20 Complejidad computacional

En caso que la entrada del algoritmo sea un número entero es importante fijar
la base con la que representaremos el número. Un número como 101 puede
estar en base 2,3, . . . ,10, . . . y su representación interna en un ordenador es
diferente según sea la base. Nosotros supondremos que todos los números
enteros están representados en base 2, que es la forma como se representan en
un ordenador.

Así, si N (N > 0) representa un número entero positivo cualquiera, el número

de bits que necesitamos para representar N es n = ⌊log2 N ⌋ + 1.

Definición 14

Cuando la entrada de un algoritmo dependa de un número entero N

(N > 0), definiremos el tamaño de la entrada como el número de bits
de la representación binaria de N.

Ejemplo 23 Criptografía

El número entero 101 en base 10 se representa como 1100101 en base 2. El número de En muchos protocolos
bits de su representación binaria es ⌊log2 101⌋ + 1 = 7. Por lo tanto, el tamaño de la criptográficos, la
entrada será n = 7. confidencialidad se garantiza
a través del tamaño de una
clave. Por ejemplo, con claves
Ejemplo 24 de 1024 bits se pueden
requerir del orden de
Supongamos que nos piden calcular la complejidad del algoritmo que suma los N (N ≥ 21024 ≈ 10308 operaciones
1) primeros números naturales. Este problema ya se trató antes* y habíamos deducido matemáticas para descifrar
que si sumábamos los N números consecutivamente entonces el algoritmo tenía una un mensaje sin tener la clave.
complejidad O(N). Si N es pequeño, entonces este cálculo se puede considerar correcto.

¿Qué pasa si N es muy grande, por ejemplo, si N es un número de 1024 bits? Entonces
es más adecuado expresar la complejidad del algoritmo en función de la longitud de
la representación binaria de N y no directamente con el valor de N. Así pues, como la
longitud binaria es n = ⌊log2 N⌋+1, este algoritmo pasaría a tener una complejidad O(2n ), *Ved el subapartado 2.2 del
dado que hay 2n números enteros diferentes de tamaño menor o igual que n. módulo “Conceptos previos:
funciones y algoritmos”.
Fijaos que este resultado pone en evidencia que este algoritmo es muy ineficiente. ¿Po-
demos pues afirmar que el problema de sumar los N primeros números naturales es un
problema intratable? Esto tampoco es cierto ya que en el módulo “Conceptos previos:
funciones y algoritmos”, habíamos visto otro algoritmo para calcular esta suma. El algo-
ritmo, propuesto por Gauss, es muy eficiente ya que tiene una complejidad polinómica
(sólo realiza una suma, un producto y una división por 2). Por lo tanto, la existencia del
algoritmo de Gauss nos confirma que este problema es tratable.

Ejercicios

9. Tenemos un algoritmo con complejidad temporal O(n2 ). ¿Qué podemos decir sobre su
complejidad espacial?

10. Tenemos un algoritmo con complejidad espacial O(n). ¿Qué podemos decir sobre su
complejidad temporal?

11. ¿Puede existir un algoritmo de complejidad temporal O(2n ) y complejidad espacial O(n)?
CC-BY-NC-ND • PID_00267022 21 Complejidad computacional

12. ¿Puede existir un algoritmo de complejidad temporal O(log n) y complejidad espacial

O(n3 )?

13. ¿Por qué en las definicions de problemas tratables e intratables no se limita la compleji-
dad espacial?

14. Tenemos un problema resoluble en tiempo O(n100 ). ¿Es tratable?

2
15. Tenemos un problema resoluble en tiempo O(2n ). ¿Es intratable?

16. Sea N (N > 0) un número entero y sea A un algoritmo que tiene como entrada el número
entero N. Calculad, en función de la longitud de la representación binaria de N, la comple-
jidad del algoritmo A para cada uno de los casos siguientes:

a) A tiene una complejidad O(N).

b) A tiene una complejidad O(N 2 ).

c) A tiene una complejidad O(log N).

d) A tiene una complejidad O(N!).

Soluciones

9. La complejidad espacial será como mucho O(n2 ), pero podría ser inferior.

10. Es como mínimo O(n), pero es posible que hagan falta más de O(n) pasos de cálculo para
llegar a la solución.

11. Sí.

12. No, porque este algoritmo no realiza suficientes pasos para poder leer o escribir toda la
memoria que supuestamente consume.

13. No se impone explícitamente ninguna restricción sobre el espacio porque las restriccio-
nes ya vienen implícitas por la complejidad temporal: si un problema es resoluble en tiempo
polinómico, necesariamente es resoluble en espacio polinómico, y pasa lo mismo con tiem-
po exponencial.

14. Sí, ya que es resoluble en tiempo polinómico: aunque el exponente del polinomio sea
una constante muy grande, el coste O(n100 ) sigue siendo polinómico.

15. No lo sabemos. Sabemos que es resoluble en tiempo exponencial, pero para ser intrata-
ble, nos faltaría asegurar que no es resoluble en tiempo polinómico. Que haya una solución
con complejidad exponencial, no significa que no pueda haber otra de complejidad polinó-
mica.

16. Si N es un número entero, entonces la longitud de su representación binaria será n =

⌊log2 N⌋ + 1. Como hay 2n números diferentes de tamaño menor o igual que n, obtenemos:

a) El algoritmo A tendría una complejidad O(2n ).

b) El algoritmo A tendría una complejidad O((2n )2 ) = O(22n ).

c) El algoritmo A tendría una complejidad O(log 2n ) = O(n log 2) = O(n).

d) El algoritmo A tendría una complejidad O(2n !).

CC-BY-NC-ND • PID_00267022 22 Complejidad computacional

2.2. Las clases de complejidad P y EXP

Definición 15

Una clase de complejidad C es un conjunto de problemas con una

característica común en su complejidad computacional.

Indicaremos que un problema Prob pertenece a una clase de compleji-

dad C con Prob ∈ C.

El nombre de la clase de complejidad acostumbra a indicar si se refiere a com-

plejidad temporal (con el sufijo TIME) o espacial (con el sufijo SPACE). Si no
se hace una distinción explícita entre tiempo y espacio, entenderemos que se
refiere al tiempo de cálculo.

Un primer criterio para definir clases de complejidad es la existencia de un

algoritmo que resuelve un problema con un cierto consumo de recursos. Así
pues, podemos definir las clases de problemas resolubles en tiempo y espacio
polinómico/exponencial.

Definición 16

La clase PTIME es el conjunto de todos los problemas resolubles en

tiempo polinómico. Para abreviar, nos referiremos a esta clase como P.

La clase EXPTIME es el conjunto de todos los problemas resolubles en

tiempo exponencial. Para abreviar, nos referiremos a esta clase como .

La clase PSPACE es el conjunto de todos los problemas resolubles en

espacio polinómico.

La clase EXPSPACE es el conjunto de todos los problemas resolubles en

espacio exponencial.

Ejemplo 25
Explosión combinatoria
Muchos de los problemas decisionales que conocemos pertenecen a las clases P y PSPACE.
Algunos ejemplos de problemas en estas clases serían: decidir si un número es par, si un Explosión combinatoria es el
grafo es conexo o si un vector de enteros está ordenado en orden creciente. término utilizado para
referirse al rápido crecimiento
Pondremos un ejemplo de problema que no pertenece a la clase P, el problema AJEDREZ: del número de posibles
“Dada una configuración de un tablero de ajedrez, determinar si un jugador tiene una se- soluciones respecto al
cuencia de jugadas ganadora a partir de esta configuración”. Para resolver este problema tamaño de la entrada.
es necesario explorar el árbol de posibles jugadas para los dos jugadores, que puede ser de
un tamaño exponencial respecto al tamaño del tablero. A partir de este razonamiento,
es posible demostrar que el problema AJEDREZ pertenece a . Este problema también
se puede definir para otros juegos como las damas o el go, con la misma complejidad
temporal.
CC-BY-NC-ND • PID_00267022 23 Complejidad computacional

Ejemplo 26
Entscheidungsproblem
Hay muchos otros problemas que se han clasificado dentro de las clases o EXPSPACE,
por ejemplo en el contexto de la lógica: comprobar si una propiedad expresada mediante
Entscheidungsproblem (en
una fórmula lógica es satisfactible puede requerir tiempo y/o espacio exponencial, en
castellano, problema de
función de la expresividad del lenguaje lógico utilizado (operadores lógicos permitidos,
decisión) es el nombre alemán
existencia de cuantificadores, . . . ).
oficial para el problema LPO.
En el año 1936, Alan Turing y
En el caso de la lógica también encontramos ejemplos de problemas que están fuera de
Alonzo Church demostraron
las clases y EXPSPACE. Por ejemplo, consideremos la lógica de primer orden, donde se
de forma independiente su
permite utilizar los cuantificadores universal (∀) y existencial (∃). Definimos el proble-
indecidibilidad. Sus
ma LPO de la forma siguiente: “Dada una fórmula f escrita en lógica de primer orden,
demostraciones definían un
decidir si f es un teorema”. Es decir, dada una fórmula f , nos planteamos si se puede
modelo abstracto de cálculo,
demostrar a partir de los axiomas de la lógica de primer orden. Resulta que el problema
la máquina de Turing y el
LPO es indecidible: no hay ningún procedimiento que resuelva LPO en tiempo finito
λ-cálculo respectivamente.
para cualquier entrada. Es decir, si proponemos un algoritmo para resolver este proble-
Este resultado fue
ma, necesariamente habrá algunas entradas para las que no podrá dar respuesta ni SÍ ni
revolucionario: ¡algunos
NO, porque requeriría un tiempo de cálculo infinito.
problemas no se pueden
resolver en tiempo finito!
Otro problema indecidible famoso es el problema de la parada: “Dado un programa Prog
y unos datos de entrada x, decidir si la ejecución de Prog con entrada x acaba en un
tiempo finito”. Este problema, pues, queda fuera del alcance de las clases de complejidad
que estudiamos en este módulo. Los problemas indecidibles los estudia otra rama de la
Informática Téorica, la Teoría de la Calculabilidad.

Ejemplo 27

Los problemas donde el tamaño de la solución es exponencial respecto al tamaño de

la entrada nunca estarán en P ni en PSPACE. Por ejemplo, consideremos el problema
PERMUTACION: “dada una cadena de caracteres c sin caracteres repetidos, calcular todas
las posibles permutaciones de los caracteres de c”. La solución de este problema tendrá
un tamaño exponencial respecto a la entrada, concretamente n!, siendo n el tamaño de
la entrada. Por lo tanto, este problema pertenece a y a EXPSPACE pero no a P ni a
PSPACE.

2.3. La clase de complejidad NP

Hasta ahora nos hemos planteado la complejidad temporal que representa

resolver un problema. Un aspecto muy relacionado con éste es el tiempo ne-
cesario para comprobar que la solución a un problema es correcta. Comprobar
una solución es una tarea más sencilla que calcularla y, por lo tanto, puede re-
querir menos recursos computacionales. Nos centraremos en los problemas
decisionales y descubriremos algunos problemas donde se puede comprobar
la solución de forma eficiente.

Definición 17

Sea T un conjunto, los elementos del cual se llaman testigos. Dado un

problema decisional Prob : I → {SÍ,NO}, una función verificadora es
una función v : I × T → {SÍ,NO} tal que:

• Si Prob(x) = SÍ, entonces existe algún testigo t ∈ T para el que v(x,t) =

SÍ.
• Si Prob(x) = NO, entonces v(x,t) = NO para cualquier t ∈ T .
CC-BY-NC-ND • PID_00267022 24 Complejidad computacional

Definición 18

Un problema Prob es verificable en tiempo polinómico si tiene una

función verificadora v calculable en tiempo polinómico.

De forma más coloquial, un testigo es un fragmento de información que, jun-

Observación
tamente con la entrada, nos permite validar eficientemente la solución SÍ a
un problema decisional. Fijémonos en que no nos planteamos el coste que El concepto de verificación es
asimétrico: no intentamos
puede tener calcular el testigo: sólo nos interesa el coste de validar la solución certificar las instancias con
solución NO, sólo las de
a partir del testigo.
solución SÍ.

Ejemplo 28

Consideremos el problema DUPL definido de la forma siguiente: “Dado un vector de

enteros A, decidir si contiene algún número repetido”. Definiremos una función verifi-
cadora para este problema decisional.

Cada entrada de este problema es una secuencia finita de enteros (I = Z∗ ). Para definir la
función verificadora, necesitamos elegir un conjunto de testigos T apropiado. El testigo
nos tendría que permitir comprobar que DUPL(A) = SÍ sin generar falsos positivos cuando
DUPL(A) = NO.

Intuitivamente, para demostrar que hay algún valor repetido en un vector es suficiente
indicar dos posiciones del vector con el mismo contenido. Por lo tanto, T sería el con-
junto de pares de números naturales (T = N × N) y cada testigo sería un par de posiciones
(i,j) del vector. La función de verificación v(A,(i,j)) se definiría de la forma siguiente:


SÍ Si i 6= j ∧ A[i] = A[j]
v(A,(i,j)) =
NO En otro caso.


Fijémonos que esta propuesta de función verificadora satisface las propiedades requeri-
das:

• Si DUPL(A) = SÍ (hay algún valor duplicado), existe un testigo (i,j) tal que A[i] = A[j].
Por ejemplo, para A = (3,4,17,4) el testigo (2,4) nos permitiría verificar que A[2] =
A[4].

• Si DUPL(A) = NO (no hay valores duplicados), no podremos encontrar ningún par

(i,j) tal que A[i] = A[j]. Fijémonos que la definición de v controla el caso trivial en
que i = j para que no se produzcan falsos positivos. Sin este control, para (12,8,9)
tendríamos que el testigo (1,1) verifica erróneamente la entrada.

Ejemplo 29

Para el problema SAT (problema de decisión 7), cada entrada es una fórmula booleana en
FNC. Un testigo sería una asignación de valores de verdad a las variables de la fórmula,
concretamente la asignación que satisface la fórmula.

A partir de una fórmula de entrada satisfactible y este testigo, se puede verificar que la
fórmula es satisfactible en tiempo polinómico: sólo es necesario comprobar que cada
cláusula evalúa a 1 según la asignación de valores de verdad del testigo.

Fijaos también que si la fórmula de entrada no es satisfactible, ninguna asignación de

valores de verdad a las variables conseguirá satisfacer todas las cláusulas. Por lo tanto, no
hay ningún testigo que permita verificar erróneamente una entrada con solución NO.
CC-BY-NC-ND • PID_00267022 25 Complejidad computacional

Ejemplo 30

Para el problema PARTICION (problema de decisión 8), cada entrada es un multiconjun-

′
to
P de enterosP C. Un testigo sería un subconjunto C ⊆ C, concretamente el que cumple
x∈C′ x = x∈C\C′ x.

A partir de este subconjunto C′ , se puede verificar que PARTICION(C) = SÍ comprobando

que la suma de los elementos de C′ es igual a la suma de los elementos que no están en
C′ . Esta comprobación se puede hacer en tiempo lineal. También sería necesario validar
que C′ ⊆ C, es decir, que todos los elementos de C′ estaban en el conjunto C original.
Esta comprobación también se puede hacer en tiempo polinómico.

Además, siP
P PARTICION(C) = NO tenemos que ningún subconjunto C′ de C cumplirá
x∈C′ x = x∈C\C′ x. Por lo tanto, no hay ningún testigo que permita verificar errónea-
mente una entrada con solución NO.

. Nomenclatura

Definición 19 La N de NP significa “No

determinista” y proviene del
La clase NPTIME es el conjunto de todos los problemas verificables en nombre de un modelo
abstracto de cálculo: la
tiempo polinómico. Para abreviar, nos referiremos a esta clase como NP. máquina de Turing no
determinista. NP también se
puede definir como el
conjunto de problemas
resolubles en tiempo
Ejemplo 31 polinómico sobre una
máquina de Turing no
Los problemas SAT y PARTICION pertenecen a NP, ya que como hemos visto previa- determinista.
mente (ejemplos 29 y 30) se pueden verificar en tiempo polinómico. Iremos viendo más
ejemplos de problemas NP a lo largo de este módulo.

Ejercicios

17. Demostrad que los siguientes problemas se pueden verificar en tiempo polinómico:
a) Dado un número entero positivo x, decidir si es un número compuesto (tiene dos divisores
diferentes de 1 y él mismo).

b) Dado un grafo G = (V,A) y un vértice v del grafo (v ∈ V), decidir si v forma parte de algún
ciclo dentro del grafo.

c) Dado un grafo G = (V,A), decidir si el grafo tiene al menos tres componentes conexas.
Ved también
18. Si un problema decisional pertenece a P, entonces seguro que pertenece a NP. ¿Cierto o
falso?
En el subapartado 4.2 del
19. Consideremos el problema decisional “Dado un grafo ponderado (G,ω), decidir si con- módulo “Recorridos y
tiene algún camino de longitud 100 o más”. Un posible testigo es un par de vértices (v1 ,v2 ), connectividad”, hemos visto
correspondientes a la arista de más peso del grafo G. ¿Cierto o falso? que el problema de encontrar
el camino más corto en un
grafo es un problema
tratable, resuelto por los
algoritmos de Dijkstra y
Soluciones Floyd. Pero,
sorprendentemente, el
problema de encontrar el
17. a) Un posible testigo sería un par de números enteros positivos y y z. Para comprobar el camino más largo en un
testigo, sería necesario ver que x = y · z y que y 6= 1, y 6= x. Si el número de entrada x se grafo ponderado es un
puede representar en n bits, el producto de y y z se puede realizar en tiempo O(n2 ) y la problema intratable.
comparación con 1 y x se puede hacer en tiempo O(n).

b) Un posible testigo sería la lista de vértices de un circuito dentro de G que contiene el

vértice v. Para comprobar el testigo, haría falta comprobar que v pertenece a la lista de
vértices, que los vértices de la lista son adyacentes entre sí, que no hay vértices repetidos
CC-BY-NC-ND • PID_00267022 26 Complejidad computacional

en la lista y que el último vértice de la lista es adyacente al primero. Dado que la lista
puede tener, como mucho, todos los vértices del grafo (n), la comprobación se puede
hacer en tiempo O(n log n) si el grafo se representa mediante una matriz de adyacencia.

c) Un posible testigo sería una terna de tres vértices (v1 ,v2 ,v3 ), uno de cada componente
conexa. Para comprobar el testigo, sería necesario comprobar que no hay ningún camino
entre v1 y v2 , entre v1 y v3 ni entre v2 y v3 . Podemos descubrir que estos vértices no estan
conectados asignando un peso unitario a cada arista del grafo G y aplicando el algoritmo
de Floyd: el camino más corto entre los tres vértices debería tener longitud infinita, por
lo tanto, la verificación del testigo se puede hacer en tiempo O(n3 ).

18. Cierto. El mismo algoritmo que resuelve el problema permite verificar el resultado SÍ a
partir de la entrada en tiempo polinómico.

19. Falso. Este testigo sólo permite certificar la respuesta SÍ en los casos donde la arista de
más peso del grafo tiene un peso más grande o igual que 100. Si el peso más grande de las
aristas del grafo es menor que 100, puede haber un camino que pase por diversas aristas
hasta superar el peso límite de 100.

?
2.4. Jerarquía de complejidad y la cuestión P = NP

Un ámbito importante dentro de la Teoría de la Complejidad es el estudio

de la relación entre diferentes clases de complejidad. Por ejemplo, se puede
dar el caso que todos los problemas de una clase de complejidad pertenezcan
también a otra, de forma que la primera clase esté incluida en la segunda.

Propiedad 20

Las clases de complejidad satisfacen las siguientes relaciones de inclu-

sión:

P ⊆ NP ⊆ PSPACE ⊆ ⊆ EXPSPACE

P⊂

PSPACE ⊂ EXPSPACE

EXPSPACE

PSPACE
NP

Demostración: Demostraremos algunas de estas inclusiones. En primer lugar, está claro

que P ⊆ y PSPACE ⊆ EXPSPACE por la propia definición de las clases: si un problema es
resoluble en complejidad polinómica o inferior, también será posible resolverlo en comple-
jidad exponencial o inferior. También hemos visto en el apartado anterior que P ⊆ NP.
Hemos mencionado previamente que la complejidad temporal es una cota superior de
la complejidad espacial de un algoritmo. Por lo tanto, si un problema Prob ∈ P entonces
Prob ∈ PSPACE, de forma que hemos demostrado P ⊆ PSPACE. Similarmente, podemos
demostrar ⊆ EXPSPACE.
CC-BY-NC-ND • PID_00267022 27 Complejidad computacional

Por otro lado, la inclusión P ⊂ indica que hay problemas resolubles en tiempo exponen-
cial y que no son resolubles en tiempo polinómico. Son los problemas que hemos llamado
intratables. Un ejemplo sería el problema AJEDREZ que hemos descrito en el ejemplo 25.
No demostraremos las inclusiones PSPACE ⊂ EXPSPACE y PSPACE ⊆ . Sólo resaltare-
mos esta última propiedad, que nos indica una relación nada evidente: cualquier problema
resoluble en espacio polinómico es resoluble en tiempo exponencial.

Ejemplo 32

El problema PAR descrito en el ejemplo 3 pertenece a la clase P. Por lo tanto, sin ne-
cesidad de más información, ya sabemos que PAR también pertenece a las clases NP,
PSPACE, y EXPSPACE.

Ejemplo 33

En el ejemplo 25 hemos descrito un problema AJEDREZ que pertenece a pero no a

P. Automáticamente, esta información nos permite afirmar que AJEDREZ ∈ EXPSPACE.
Sólo con estos datos, no podemos afirmar si AJEDREZ pertenece a NP o PSPACE.

En concreto, estudiaremos especialmente las relaciones entre las clases P y NP.

Lectura
Este especial interés está motivado por diversas razones: complementaria

Revisad también el artículo

• Primero, la clase NP contiene muchos problemas relevantes por su apli- de S. Cook (2003). The
cación en diferentes ámbitos (logística, planificación, diseño asistido por Importance of the P versus NP
Question. Journal of the
computador, bioinformática, criptografía, . . . ). ACM (vol. 1, núm. 50, págs.
27-29)

• En segundo lugar, aún no se ha conseguido demostrar la relación entre la

clase P y la clase NP. Es decir, hay problemas que se pueden verificar en
tiempo polinómico pero no sabemos si se pueden resolver o no en tiempo
polinómico.

• Finalmente, NP representa una frontera de la tratabilidad. Los problemas

que no pertenecen a NP son claramente intratables: si hay un problema que
ni siquiera se puede verificar eficientemente, nos podemos olvidar de re-
solverlo eficientemente. Por otro lado, los problemas de la clase NP son
potencialmente tratables: como se pueden verificar eficientemente, existe la
posibilidad de que también se puedan resolver eficientemente, aunque pa-
ra algunos problemas nuestro conocimiento aún no permita hacerlo.

Ejemplo 34

En el ejemplo 31 hemos visto que los problemas SAT y PARTICION pertenecen a la

clase NP ya que se pueden verificar eficientemente. Ahora bien, no se conoce ningún
algoritmo eficiente que los resuelva: los mejores algoritmos conocidos tienen un tiem-
Problema del milenio
po de ejecución exponencial. Por otro lado, la teoría no impide que haya algoritmos
más eficientes para SAT y PARTICION que los actuales. ¡Quizás existen y aún no se han
encontrado! El año 2000, el Clay
Mathematics Institute
denominó a la cuestión
P = NP? uno de los
Precisamente la relación entre las clases P y NP es uno de los problemas abier- “problemas del milenio” y
tos más importantes del campo de la Informática Teórica. Como ya sabemos ofrece 1 millón de dólares a
quién consiga resolverlo.
que P ⊆ NP, la duda está en si NP ⊆ P. Dicho de otra forma, nos pregunta-
CC-BY-NC-ND • PID_00267022 28 Complejidad computacional

mos si podemos resolver en tiempo polinómico todos los problemas que se

?
pueden verificar en tiempo polinómico, es decir, si P = NP. Algunas formula-
ciones equivalentes de esta pregunta serían:

• ¿Son tratables todos los problemas de NP?

• ¿Hay algún problema que esté en NP pero no en P (NP \ P 6= ∅)?

Aunque a lo largo de los años se han hecho numerosas propuestas de demos-

tración para esta cuestión, tanto afirmando que P = NP como que P 6= NP,
actualmente no hay ninguna demostración aceptada sobre la relación entre
P y NP. Las evidencias existentes parecen apuntar hacia P 6= NP, ya que una
confirmación de que P 6= NP no tendría consecuencias muy importantes. En
cambio, si se demuestra que P = NP, este hecho tendría enormes repercusiones
sobre la Informática: muchos problemas que hasta ahora se han considerado
difíciles o que no se pueden resolver de forma práctica pasarían a poderse
resolver de forma eficiente.

Por poner sólo un ejemplo, la criptografía de clave pública basa su seguridad

en la existencia de problemas computacionalmente complejos. La existencia
de algoritmos eficientes para resolver estos problemas reduciría enormemente
el coste de descifrar cualquier mensaje. Esto podría comprometer la seguridad
de algunos criptosistemas de clave pública utilizados en la actualidad.

Ejercicios

20. Para cada uno de los siguientes problemas, indicad a qué clases de complejidad debe
pertenecer necesariamente, a cuáles puede pertenecer y a cuáles seguro que no pertenece:
a) Un problema que se puede resolver en espacio O(n3 ).

b) Un problema que se puede verificar en tiempo O(n5 log n).

c) Un problema que se puede verificar en tiempo O(3n ).

d) Un problema que no se puede resolver en tiempo polinómico.

21. Si P = NP, entonces P = PSPACE. ¿Cierto o falso?

22. Si P = PSPACE, entonces P = NP. ¿Cierto o falso?

23. Podemos afirmar que P 6= EXPSPACE. ¿Cierto o falso?

24. Tenemos un problema de NP que se puede resolver en tiempo polinómico. ¿Quiere decir
esto que P = NP?

Soluciones

20. Fijémonos que el hecho de que haya una determinada solución no impide que haya otras
más o menos eficientes, a menos que el enunciado lo indique explícitamente. Otro aspecto
relevante a destacar es que la verificación en tiempo exponencial no nos aporta información
sobre la clase de complejidad de un problema.
CC-BY-NC-ND • PID_00267022 29 Complejidad computacional

Problema P NP PSPACE EXPSPACE

a Puede Puede Sí Sí Sí
b Puede Sí Sí Sí Sí
c Puede Puede Puede Puede Puede
d No Puede sólo si P 6= NP Puede Puede Puede

21. Falso. P y NP son dos subclases de PSPACE y el hecho que sean iguales entre sí no nos
indica nada respecto a la superclase PSPACE.

22. Cierto. La inclusión NP ⊆ PSPACE hace que si P = PSPACE entonces P = NP.

23. Cierto. Sabemos que P ⊂ , y como ⊆ EXPSPACE podemos concluir que P 6= EXPSPACE.

24. Esto no quiere decir que P = NP. Dado que P ⊆ NP, es normal encontrar dentro de
NP problemas que se pueden resolver en tiempo polinómico, es decir, problemas de P. Para
demostrar que P = NP sería necesario demostrar que todos los problemas de NP se pueden
resolver en tiempo polinómico.
CC-BY-NC-ND • PID_00267022 30 Complejidad computacional

3. Reducciones y completitud
.

En este apartado estudiaremos la complejidad relativa de dos problemas di-

ferentes, entendida como la comparación entre los recursos necesarios para
resolver los dos problemas. Dados dos problemas A y B, nos plantearemos
cuestiones como “¿es A más complejo que B?” o “¿es A igual de complejo que B?”.
Estas preguntas nos permitirán clasificar la complejidad de un problema nue-
vo a partir de problemas conocidos, así como identificar los problemas más
difíciles dentro de una clase de complejidad.

3.1. El concepto de reducción polinómica

Hay problemas decisionales que están estrechamente relacionados. En algu-

nos de estos casos, el mismo algoritmo que resuelve un problema se puede
utilizar para resolver otros problemas similares, realizando sólo un preproceso
a la entrada.

Ejemplo 25

Si tenemos un algoritmo para decidir si un número entero es positivo, lo podemos

reaprovechar para decidir si un número entero es negativo: sólo necesitamos multiplicar
la entrada por –1 antes de ejecutar el algoritmo.

. Atención!

Definición 21 El orden de los problemas A y

B en una reducción es
Una reducción del problema A al problema B es una función f : IA → relevante: A ≤p B no es lo
mismo que B ≤p A.
IB que transforma cada entrada del problema A (x ∈ IA ) en una entrada
del problema B (f (x) ∈ IB ) de forma que se cumple A(x) = B(f (x)).

Si además hay un algoritmo que calcula f en tiempo polinómico, dire-

mos que f es una reducción polinómica del problema A al problema
B y lo denotaremos como A ≤p B.

Algoritmo que resuelve A

SÍ
ր
x ∈ IA –→ f –→ f (x) ∈ IB –→ Algoritmo que resuelve B
ց
NO
CC-BY-NC-ND • PID_00267022 31 Complejidad computacional

Intuitivamente, la reducción es un preproceso que nos permite reaprovechar

el algoritmo que resuelve el problema B para resolver el problema A sin nin-
guna otra modificación al algoritmo. Veamos algunos ejemplos de funciones
que son reducciones y de funciones que no lo son.

Ejemplo 36

Disponemos de un algoritmo muy eficiente para resolver el problema PAR y queremos

reaprovecharlo para resolver el problema IMPAR: “Dado un número natural x, decidir
si es impar”. Un posible algoritmo que calcularía la solución de IMPAR podría ser el
siguiente: calcular la solución de PAR con entrada x + 1. Gráficamente, representaríamos
esta reducción así:

SÍ
x+1 PAR ր
x ∈ N –→ –→ x + 1 ∈ N –→
ց
NO

Fijémonos que este algoritmo calculará la solución correcta para todas las entradas del
problema IMPAR, es decir, que IMPAR(x) = PAR(x + 1) para cualquier x. De cara a demos-
trar esta igualdad, es necesario considerar dos tipos de entradas: las que tienen solución
SÍ y las que tienen solución NO.

• Caso IMPAR(x) = SÍ: Hay que demostrar que PAR(x + 1) = SÍ.

Cierto. Como x es un número impar, entonces x+1 será par (PAR(x+1) = SÍ). Tenemos
pues que IMPAR(x) = PAR(x + 1).

• Caso IMPAR(x) = NO: Hay que demostrar que PAR(x + 1) = NO.

Cierto. Como x es un número par, entonces x + 1 será impar (PAR(x + 1) = NO).

Volvemos a tener que IMPAR(x) = PAR(x + 1).

En este caso, la función de reducción utilizada ha sido f (x) = x + 1. Es una función que se
puede calcular en tiempo polinómico y, por lo tanto, podemos decir que IMPAR ≤p PAR.

Ejemplo 37

Supongamos que queremos hacer una reducción de PRIMO (“dado un número natural
x, decidir si tiene exactamente dos divisores: 1 y x”) al problema IMPAR. Proponemos
como función de reducción f (x) = x + 2. Comprobemos si es una reducción correcta:

• Caso PRIMO(x) = SÍ: Hay que demostrar que IMPAR(x + 2) = SÍ.

Falso. Por ejemplo x = 2 es un número primo (PRIMO(2) = SÍ) pero x + 2 = 4 no es

impar (IMPAR(4) = NO).

• Caso PRIMO(x) = NO: Hay que demostrar que IMPAR(x + 2) = NO.

Falso. Por ejemplo x = 1 no es un número primo (PRIMO(1) = NO) pero x + 2 = 3 sí

es impar (IMPAR(3) = SÍ).

Vemos pues que f no es una reducción. Intentemos definir una función más complicada
para hacer la reducción de PRIMO a IMPAR que resuelva estos problemas detectados:


2 Si x = 1



g(x) = 3 Si x = 2



x En otro caso.

CC-BY-NC-ND • PID_00267022 32 Complejidad computacional

Comprobemos ahora si g es una reducción correcta:

• Caso PRIMO(x) = SÍ: Hay que demostrar que IMPAR(g(x)) = SÍ.

Cierto. Si un número es primo, entonces tiene que ser impar, con la excepción del 2,
pero la función g ya lo trata como un caso especial: PRIMO(2) = IMPAR(3) = SÍ.

• Caso PRIMO(x) = NO: Hay que demostrar que IMPAR(g(x)) = NO.

Falso. La igualdad se cumple para x = 4 pero hay números compuestos que son
impares, como por ejemplo 15 = 3 · 5: PRIMO(15) = NO, IMPAR(15) = SÍ.

La función g tampoco nos sirve como reducción, ya que no preserva la solución para las
entradas con solución NO (aunque sí se comporta correctamente para entradas con solu-
ción SÍ). Fijémonos pues que, al definir una reducción, siempre tenemos que comprobar
tanto la solución SÍ como la solución NO por separado.

Ejercicios

25. Sea MULT4 el problema “Dado un número natural x, decidir si es un múltiplo de 4.”
Proponed reducciones polinómicas para IMPAR ≤p MULT4, PAR ≤p MULT4, MULT4 ≤p PAR
y MULT4 ≤p IMPAR y demostrad que son correctas.

26. Sea Prob un problema cualquiera. ¿Podemos definir una reducción Prob ≤p Prob? ¿Qué
función de reducción tendríamos que utilizar?

27. Ahora recuperemos los problemas SUMA_SUB (problema de decisión 9) y PARTICION

(problema de decisión 8). Proponemos la siguiente reducción SUMA_SUB ≤p PARTICION:
f (C,t) = C ∪ {s – 2t}, donde s es la suma de todos los elementos de C. ¿Es f una reducción
polinómica? Justificad la respuesta.

28. Queremos hacer la reducción inversa, PARTICION ≤p SUMA_SUB, y proponemos como

función de reducción: f (C) = (C,s div 2), donde s es la suma de todos los elementos de C y
div es la división entera. ¿Es f una reducción polinómica? Justificad la respuesta.

Soluciones

25. Proponemos las reducciones siguientes:

• PAR ≤p MULT4: f (x) = 2x.
Si x es par, entonces 2x será múltiplo de 4. En cambio, si x es impar, 2x será par pero no
será múltiplo de 4.

• IMPAR ≤p MULT4: g(x) = 2(x + 1).

Si x es impar, x + 1 será par y por lo tanto 2(x + 1) será múltiplo de 4. Igual que antes, si x
no es impar, x + 1 será impar y 2(x + 1) será par pero no múltiplo de 4.

• MULT4 ≤p PAR: h(x) = (x div 2)(1–(x m«od 2)) , donde div es la división entera y m«
od es el
resto de la división.
Si x es múltiplo de 4, el cociente será un número par y el resto será 0, y por lo tanto
h(x) será par. En cambio, si x no es múltiplo de 4 puede pasar que el resto sea 1 (por
ejemplo, x = 13) o que el cociente sea impar (por ejemplo, para x = 30). Si el resto es
1, independientemente de como sea el cociente, tendremos h(x) = (x div 2)0 = 1 y por
lo tanto h(x) no es un número par. Si el resto es 0 y el cociente es impar, tenemos que
h(x) = (x div 2)1 = x div 2 que como hemos dicho es un número impar. Por lo tanto, si x
no es múltiplo de 4, tenemos que h(x) no es par.

• MULT4 ≤p IMPAR: m(x) = h(x) + 1.

La demostración es equivalente a la que hemos hecho en la reducción anterior.

Todas las funciones propuestas son calculables en tiempo polinómico.

CC-BY-NC-ND • PID_00267022 33 Complejidad computacional

26. La reducción Prob ≤p Prob siempre se puede definir, independientemente de quién sea el
problema Prob. La función de reducción que utilizaríamos sería la función identidad f (x) = x,
que tiene coste constante y garantiza que A(x) = A(f (x)).

27. En primer lugar, podemos ver que f es calculable en tiempo polinómico: se calcularía
haciendo un recorrido sobre el conjunto C, haciendo una suma para cada elemento y, al
final, una resta y un producto.
Ahora nos falta demostrar que SUMA_SUB(C,t) = PARTICION(f (C,t)) para aquellas entradas
con soluciones SÍ y aquellas con solución NO:

• Caso SUMA_SUB(C,t) = SÍ: Hay que demostrar que PARTICION(f (C,t)) = SÍ.

SUMA_SUB(C,t) = SÍ significa que tenemos un subconjunto X ⊆ C tal que la suma de

sus elementos es t. Como s está definido como la suma de todos los elementos de C,
el complementario de X, X, tendrá como sumatorio de sus elementos s – t. Entonces,
C ∪ {s – 2t} se puede particionar de la forma siguiente: X y X ∪ {s – 2t}. Fijémonos que
las dos particiones tienen suma total s – t, de manera que PARTICION(f (C,t)) = SÍ.

• Caso SUMA_SUB(C,t) = NO: Hay que demostrar que PARTICION(f (C,t)) = NO.

Suponemos que PARTICION(f (C,t)) = SÍ y SUMA_SUB(C,t) = NO y llegaremos a una

contradicción. La suma total de los elementos de f (C,t) es 2s – 2t y, por lo tanto, si hay
una partición de C ∪ {s – 2t}, la suma de los elementos de cada partición debe ser s – t.
Si nos fijamos en la partición que contiene el número s – 2t, el resto de elementos de
la partición deben sumar t. Pero esto significa que hay un subconjunto de C que tiene
como suma total t, contradiciendo la hipótesis que SUMA_SUB(C,t) = NO.

28. La reducción propuesta va bien encaminada pero tiene dos errores. En primer lugar, f
no preserva la solución cuando la suma s tiene un valor impar. Por ejemplo, si C = [3,4,8],
tenemos que PARTICION(C) = NO, pero en cambio SUMA_SUB({3,4,8},7) = SÍ.
Finalmente, la reducción tiene otro error más sutil: el problema PARTICION tiene como en-
trada un multiconjunto de enteros (donde se admiten repeticiones) mientras que SUMA_SUB
espera recibir como entrada un conjunto de enteros (y por lo tanto, no admite repeticiones).
Por lo tanto, la función f (C) = (C,s div 2) no siempre nos retorna una entrada correcta de
SUMA_SUB para cualquier entrada de PARTICION.

3.2. Propiedades de las reducciones, transitividad

y equivalencia

El concepto de reducción es muy importante por dos motivos, uno más prác-
tico y otro más teórico.

En primer lugar, las reducciones nos permiten reaprovechar algoritmos cono- ¿El mejor solver?
cidos para la resolución de nuevos problemas. Esta reutilización es especial-
Desde el año 2002, se realiza
mente ventajosa cuando el algoritmo es muy eficiente o cuando su imple- una competición científica
mentación es muy costosa. Por ejemplo, en la actualidad, gran cantidad de anual donde se compara la
eficiencia de los solvers de
problemas complejos se resuelven traduciéndolos a SAT. Los solvers de SAT es- SAT más recientes:
tán muy optimizados, de forma que es más práctico traducir un problema a [Link]
.[Link].
SAT que desarrollar soluciones a medida para cada nuevo problema.

En segundo lugar, una reducción establece una relación entre las complejida-
des de los problemas involucrados. Con A ≤p B, estamos diciendo que una
forma de resolver A es calcular la función de reducción f y después resol-
ver B.

• En una dirección, esto fija una cota superior para la complejidad del pro-
blema A: como máximo, A se puede resolver en el tiempo que se tarda
CC-BY-NC-ND • PID_00267022 34 Complejidad computacional

en calcular la función de reducción más el tiempo de resolver B. No esta-

mos diciendo que esta sea la forma más eficiente de resolver A, pero como
mínimo sabemos que tenemos esta forma de resolverlo.

• En la direcció opuesta, A ≤p B también nos fija una cota inferior a la com-

plejidad de B: ¡calcular B(f (x)) no puede ser más eficiente que calcular A(x),
como mínimo será igual de eficiente! Por lo tanto, si sabemos que A es un
problema muy complejo, no es posible que B se pueda resolver de forma
muy eficiente.

Utilizando estas propiedades de las reducciones es posible identificar la clase

de complejidad de un problema comparándolo con problemas conocidos. A
continuación, enunciamos formalmente estas dependencias que aparecen al
hacer una reducción.

. Observación

Propiedad 22 Notad que la relación A ≤p B

denota que “el problema B
Si A ≤p B, entonces: es al menos tan difícil como
el problema A” o, enunciado
de otra forma, “el problema
1) B ∈ P → A ∈ P (Si B pertenece a P, entonces A también) A no es más difícil que el
problema B”.
2) B ∈ NP → A ∈ NP (Si B pertenece a NP, entonces A también)

3) A ∈/ P → B ∈/ P (Si A no pertenece a P, entonces B tampoco)

4) A ∈/ NP → B ∈/ NP (Si A no pertenece a NP, entonces B tampoco)

Demostración: Demostremos que si A ≤p B y A ∈ / P entonces B ∈ / P (el resto de propieda-

des se demostrarían de forma similar). Procedemos por reducción al absurdo: supondremos
que A ∈/ P y B ∈ P y llegaremos a una contradicción.
Como B ∈ P, sabemos que B(x) es calculable en tiempo polinómico. Además, como
A ≤p B, sabemos que hay una función f calculable en tiempo polinómico que permite
expresar A en términos de B: A(x) = B(f (x)). Pero como B y f se pueden calcular en tiempo
polinómico, tenemos que B(f (x)) también se puede calcular en tiempo polinómico. Esto
querría decir que A ∈ P, contradiciendo la hipótesis inicial que A ∈
/ P.

Ejemplo 38

Supongamos que tenemos una reducción SUMA_SUB ≤p PARTICION como la del ejer-
cicio 27. Como sabemos que PARTICION ∈ NP, automáticamente SUMA_SUB ∈ NP. Si
descubriéramos que SUMA_SUB ∈ / P, entonces sabríamos que PARTICION ∈
/ P.

Las conclusiones sólo se aplican en una dirección: si averiguamos que PARTICION ∈

/ P,
esta reducción no nos aporta ninguna información sobre SUMA_SUB. Igualmente, si
averiguamos que SUMA_SUB ∈ NP, esta reducción no nos informa sobre la complejidad
de PARTICION.
CC-BY-NC-ND • PID_00267022 35 Complejidad computacional

Propiedad 23

La reducción polinómica es transitiva: dados tres problemas A, B y C,

si A ≤p B y B ≤p C, entonces tenemos que A ≤p C.

Demostración: Para demostrar que existe la reducción A ≤p C, tenemos que construir una
función f calculable en tiempo polinómico tal que A(x) = C(f (x)).
La reducción A ≤p B nos asegura que existe una función g calculable en tiempo poli-
nómico tal que A(x) = B(g(x)). Igualmente, con la reducción B ≤p C, sabemos que hay una
función h calculable en tiempo polinómico tal que B(x) = C(h(x)). La función f que estamos
buscando es precisamente la composición de estas funciones g y h: A(x) = B(g(x)) = C(h(g(x))).
Además, como f (x) = h(g(x)) y g y h tienen complejidad polinómica, f también tiene
complejidad polinómica.

Definición 24

Dos problemas decisionales A y B son polinómicamente equivalentes

cuando A ≤p B y B ≤p A.

Ejemplo 39

Los problemas IMPAR y PAR son polinómicamente equivalentes entre sí. Curiosamente,
la misma función f (x) = x + 1 que hace la reducción IMPAR ≤p PAR permite hacer
la reducción PAR ≤p IMPAR. Normalmente no tendremos esta suerte y necesitaremos
definir una función de reducción diferente para cada dirección de la reducción.

Ejemplo 40

Todos los problemas de la clase P (con dos excepciones que mencionaremos a continua-
ción) son polinómicamente equivalentes entre sí. Una función de reducción genérica
A ≤p B entre cualquier par de problemas A y B de la clase P se construiría de la forma
siguiente.

Primero, elegimos dos entradas del problema B, una con solución SÍ (ys ∈ IB ,B(ys ) = SÍ)
y la otra con solución NO (yn ∈ IB ,B(yn ) = NO). Qué entradas elijamos es indiferente,
sólo nos preocupa cuál es su solución. Entonces, la función de reducción f (x) se definiría
como:


y Cuando A(x) = SÍ
s
f (x) =
yn Cuando A(x) = NO


Es decir, en primer lugar resolvemos el problema A y devolvemos una entrada precalcula-

da del problema B que sabemos que tiene la misma solución. Esta función f es calculable
en tiempo polinómico porque A ∈ P.

Para poder definir esta función f necesitamos que el problema B tenga alguna entrada
con solución SÍ y alguna entrada con solución NO. Precisamente, los dos problemas de P
donde no se puede establecer esta reducción son dos problemas definidos en el ejemplo
6: ProbSI, el problema con solución SÍ para todas las entradas y ProbNO, el problema con
solución NO para todas las entradas.
CC-BY-NC-ND • PID_00267022 36 Complejidad computacional

Ejercicios

30. Recordad el problema AJEDREZ definido en el ejemplo 25. ¿Es posible definir una re-
ducción AJEDREZ ≤p PAR? ¿Y PAR ≤p AJEDREZ?

31. En el ejercicio 27 hemos visto cómo hay que hacer la reducción polinómica SUMA_SUB ≤p
PARTICION. ¿Qué información nos aporta sobre la complejidad de estos problemas?

32. Todo problema es polinómicamente equivalente a sí mismo. ¿Cierto o falso?

Soluciones

30. La reducción AJEDREZ ≤p PAR es imposible. Como PAR ∈ P, las propiedades de las
reducciones nos llevarían a afirmar que AJEDREZ ∈ P. Pero hemos visto previamente que
AJEDREZ no se puede resolver en tiempo polinómico y, por lo tanto, no es posible hacer la
reducción.
En cambio, la reducción contraria PAR ≤p AJEDREZ es factible según las propiedades de
las reducciones (PAR ∈ P, AJEDREZ ∈ ). La reducción f (x) se podría hacer de la forma
siguiente: si x es par, retorna un tablero de ajedrez donde el rey negro está rodeado de 9
reinas blancas (jaque mate en un movimiento); si x es impar, entonces retorna un tablero de
ajedrez donde sólo queda el rey blanco y el rey negro (es imposible ganar la partida).

31. Sabemos que PARTICION ∈ NP y, por lo tanto, podemos afirmar que SUMA_SUB ∈ NP
(dato que también podemos obtener definiendo el algoritmo verificador para SUMA_SUB).
Por otro lado, si consiguiéramos demostrar que SUMA_SUB ∈ / P, entonces sabríamos que
PARTICION ∈ / P. Pero de momento no se ha conseguido averiguar si SUMA_SUB pertenece
a P.

32. Cierto, ya que para cualquier problema Prob tenemos Prob ≤p Prob utilizando como
función de reducción la función identidad f (x) = x.

3.3. Completitud

Definición 25

Sea C una clase de complejidad y sea Prob un problema. Prob es un

problema C-Difícil si cualquier problema de la clase C se puede reducir
polinómicamente a Prob, es decir:

Prob es C-Difícil ↔ ∀A ∈ C : A ≤p Prob

Si, además de ser C-Difícil, Prob ∈ C, diremos que Prob es un problema

C-Completo.

Intuitivamente, un problema C-Difícil es tan o más complejo que cualquiera

de la clase C, ya que todos ellos se pueden resolver en base a éste. En el caso
de un problema C-Completo, como además pertenece a la clase C, es uno de
Nomenclatura
los problemas que comparten la complejidad máxima dentro de esta clase.
En inglés, NP-Completo se
llama NP-Complete y
Aunque el concepto de C-Difícil y C-Completo se puede aplicar a cualquier NP-Difícil se llama NP-Hard.
clase de complejidad, lo utilizaremos especialmente para referirnos a las clases
CC-BY-NC-ND • PID_00267022 37 Complejidad computacional

NP y . Así pues, hablaremos de problemas NP-Difíciles, NP-Completos, -

Difíciles o -Completos.

.
Lectura
Teorema 26 complementaria

Teorema de Cook: El problema SAT es NP-Completo. La demostración del

teorema de Cook se puede
encontrar en los libros de
Garey y Johnson (1979) y
Papadimitriou (1994).

Demostración: Este teorema, demostrado en 1971, es uno de los resultados fundamen-

tales de la Teoría de la Complejidad. Aparte de justificar que SAT ∈ NP como ya hemos
visto previamente, Cook demostró que cualquier problema NP se puede codificar de forma
equivalente como una fórmula booleana en FNC, y que este proceso de codificación tenía
complejidad polinómica. La demostración es larga y compleja y no la veremos aquí.

Ejemplo 41

Los problemas PARTICION y SUMA_SUB también son problemas NP-Completos (no ve-
remos la demostración).

Las propiedades de las reducciones, como por ejemplo la transitividad, per-

miten extraer algunas propiedades interesantes de los problemas completos y
difíciles. Por ejemplo, nos proporcionan mecanismos para identificar nuevos
problemas completos y difíciles a partir de problemas difíciles conocidos.

Propiedad 27

Todos los problemas C-Completos de una clase de complejidad C son

polinómicamente equivalentes entre sí.

Demostración: Sean A y B dos problemas C-Completos. Sabemos que todos los problemas
de la clase C se tienen que reducir polinómicamente tanto a A como a B. Además, al ser
A y B completos, ambos problemas pertenecen a C (A,B ∈ C). Esto significa que existen
las reducciones A ≤p B (ya que A ∈ C y B es C-Completo) y B ≤p A (ya que B ∈ C y
A es C-Completo). Como existen A ≤p B y B ≤p A, hemos demostrado que A y B son
polinómicamente equivalentes.
Fijaos que este razonamiento no permitiría demostrar que todos los problemas C-Difíciles
son polinómicamente equivalentes entre sí (propiedad totalmente falsa), ya que no podría-
mos asegurar que A,B ∈ C.

Propiedad 28

Sea C una clase de complejidad y Prob un problema C-Difícil. Si tenemos

un problema A tal que Prob ≤p A, entonces A también es C-Difícil.
CC-BY-NC-ND • PID_00267022 38 Complejidad computacional

Demostración: Necesitamos demostrar que, dado cualquier problema B ∈ C, podemos

hacer una reducción B ≤p A. Para hacer la demostración, utilizaremos la propiedad transitiva
de las reducciones.
En primer lugar, sabemos que Prob es C-Difícil. Esto quiere decir que para cualquier
problema B ∈ C, podemos hacer una reducción B ≤p Prob. Como según la hipótesis tenemos
la reducción Prob ≤p A, por transitividad podemos asegurar que existe la reducción B ≤p A.

Esta propiedad nos ofrece una forma sencilla de demostrar que un problema
es difícil respecto a una clase: en lugar de tener que demostrar que todos los
problemas de la clase se pueden reducir a él, es suficiente construir una sola
reducción a partir de un problema difícil previamente conocido.

Ejemplo 42

A partir del teorema de Cook se puede demostrar que el problema 3SAT es NP-Difícil
si definimos una reducción SAT ≤p 3SAT. En SAT las cláusulas pueden tener cualquier
número de literales, mientras que 3SAT es una versión restringida del problema donde
todas las cláusulas tienen exactamente tres literales. Por lo tanto, cada cláusula de SAT
se tiene que transformar en un conjunto equivalente de cláusulas de tres literales. Parece
lógico que el procedimiento de traducción distinga cuatro casos de cláusulas de SAT: las
de un literal, las de dos literales, las de tres literales y las de cuatro o más literales.

Utilizamos las letras a,b,ai ,... para indicar los literales de las cláusulas SAT. Al hacer la
traducción a 3SAT tendremos que introducir nuevas variables en la fórmula, que deno-
minaremos mediante las letras α,β,αi ,...

Literales Cláusula de SAT Cláusulas en 3SAT

1 (a) (a ∨ α ∨ β) ∧ (a ∨ α ∨ β) ∧ (a ∨ α ∨ β) ∧
(a ∨ α ∨ β)
2 (a ∨ b) (a ∨ b ∨ α) ∧ (a ∨ b ∨ α)
3 (a ∨ b ∨ c) (a ∨ b ∨ c)
4 o más (a1 ∨ a2 ∨ . . . ∨ ak ) (a1 ∨ a2 ∨ α1 ) ∧ (a3 ∨ α1 ∨ α2 ) ∧ . . . ∧
(ak–2 ∨ αk–4 ∨ αk–3 ) ∧ (ak–1 ∨ ak ∨ αk–3 )

La fórmula 3SAT resultante sería la conjunción de las traducciones de todas las cláusulas
SAT. Una vez propuesta la función f de reducción SAT ≤p 3SAT, nos hace falta compro-
bar que es una reducción correcta. Los dos pasos para hacerlo son (1) demostrar que f se
puede calcular en tiempo polinómico y (2) demostrar que SAT(x) = 3SAT(f (x)).

El tiempo de cálculo polinómico se puede justificar fácilmente. Supongamos que la fór-

mula SAT de partida tiene n cláusulas y un máximo de k literales por cláusula. La tra-
ducción hace un recorrido de las cláusulas (tiempo O(n)) y en cada cláusula hace una
traducción que genera, según el número de literales de la cláusula, 4, 2, 1 o k – 2 nuevas
cláusulas (tiempo O(k)). Por lo tanto, la traducción se realiza en tiempo polinómico.

Pasemos pues a demostrar la equivalencia. La idea de la traducción es utilizar variables

auxiliares para crear cláusulas de tres literales equivalentes a las de partida en SAT. Cuan-
do hay 1 o 2 literales en la cláusula, la equivalencia es clara: introducimos tantas varia-
bles nuevas como literales falten para llegar a 3 y generamos tantas cláusulas como hagan
falta para generar las posibles combinaciones de estas nuevas variables (4 y 2 respectiva-
mente). Las cláusulas ya inicialmente de tres literales en SAT sirven tal y como están en
el problema 3SAT y no es necesario modificarlas.

En el último caso con 4 o más literales, hacemos la demostración detalladamente:

• Caso SAT(x) = SÍ: Algún literal ai tiene que evaluar a 1. Si fijamos todas las variables αi
a 0 excepto la que aparezca sin negar en la misma cláusula que ai podremos satisfacer
todas las cláusulas de f (x) y, por lo tanto, 3SAT(f (x)) = SÍ.

• Caso SAT(x) = NO: No hay ningún literal ai que se satisfaga y, por lo tanto, f (x) sólo
podría satisfacerse usando los literales αi . Tenemos suficiente con ver que siempre
CC-BY-NC-ND • PID_00267022 39 Complejidad computacional

queda alguna cláusula en 3SAT sin satisfacer. El razonamiento sería el siguiente: para
satisfacer la primera cláusula, α1 tiene que ser 1 ya que los literales ai son todos
0; entonces, para satisfacer la segunda cláusula, α2 tiene que ser 1; seguiendo así,
llegamos a la última cláusula teniendo que αk–3 tiene que ser 1 y, por lo tanto, no se
satisface la última cláusula. Así pues, hemos demostrado que 3SAT(f (x)) = NO.

En definitiva, hemos construido la reducción SAT ≤p 3SAT. Como sabemos que SAT es
NP-Difícil, podemos concluir que 3SAT es NP-Difícil.

Se podría ir más allá y demostrar que 3SAT es NP-Completo además de NP-Difícil. Para
demostrarlo sólo nos faltaría ver que el problema 3SAT pertenece a NP, es decir, que se
puede verificar en tiempo polinómico (repasad el ejercicio de autoevaluación 4).

Corolario 29

Si Prob es un problema NP-Completo cualquiera, entonces Prob ∈ P si y

sólo si P = NP.

Demostración: Tenemos que demostrar dos cosas: si Prob ∈ / P entonces P 6= NP y si Prob ∈

P entonces P = NP.
La primera demostración es directa: como Prob es un problema NP-Completo, Prob ∈ NP.
Como Prob pertenece a NP pero no pertenece a P, tenemos que P 6= NP.
La segunda demostración es más interesante: si Prob ∈ P, entonces podemos demostrar
que cualquier problema NP es resoluble en tiempo polinómico. Sea A un problema NP cual-
quiera, entonces describiremos el algoritmo que lo calcularía:

• Como Prob ∈ P (según la hipótesis), Prob(x) se puede calcular en tiempo polinómico.

• Como Prob es NP-Completo y A ∈ NP, existe una reducción polinómica A ≤p Prob. Es

decir, hay una función f calculable en tiempo polinómico tal que A(x) = Prob(f (x)).

• Como tanto Prob como f se pueden calcular en tiempo polinómico, tenemos que A(x) =
Prob(f (x)) se puede calcular en tiempo polinómico y, por lo tanto, A ∈ P.

Este último corolario nos aporta un posible método para decidir la cuestión
?
P = NP: sólo necesitaríamos demostrar la pertenencia de un problema NP-
Completo en la clase P (o su no pertenencia) para concluir que P = NP (res-
pectivamente, P 6= NP). Es decir, si encontráramos un algoritmo que resolviera
un problema NP-Completo en tiempo polinómico o bién demostráramos que
no hay ninguno, habríamos resuelto uno de los problemas abiertos más im-
portantes del campo de la Informática Teórica.

Ejercicios

32. Demostrad que la propiedad “ser polinómicamente equivalente” es transitiva, es decir,

que si tenemos tres problemas A, B y C con A polinómicamente equivalente a B y B polinó-
micamente equivalente a C, entonces A y C son polinómicamente equivalentes.

33. Según hemos definido las reducciones polinómicas, ¿qué problemas de la clase P son
P-Completos? ¿Y qué problemas de la clase NP son P-Completos?

34. ¿Una reducción PAR ≤p SAT nos permite demostrar que P = NP? ¿Y una reducción
SAT ≤p PAR?

35. Todo problema NP-Difícil tiene que ser NP-Completo. ¿Cierto o falso?
CC-BY-NC-ND • PID_00267022 40 Complejidad computacional

Soluciones

32. Tenemos que demostrar que existen dos reducciones polinómicas A ≤p C y C ≤p A. Para
hacerlo, nos aprovecharemos de la propiedad transitiva de las reducciones:

• Como A y B son polinómicamente equivalentes, tenemos A ≤p B y B ≤p A.

• Como B y C son polinómicamente equivalentes, tenemos B ≤p C y C ≤p B.

• Como tenemos las reducciones C ≤p B y B ≤p A, por transitividad tenemos la reducción

C ≤p A.

• Como tenemos las reducciones A ≤p B y B ≤p C, por transitividad tenemos la reducción

C ≤p A.

• Como tenemos las reducciones A ≤p C y C ≤p A, entonces A y C son polinómicamente

equivalentes.

33. Todos los problemas de la clase P son P-Completos, excepto dos problemas: ProbSI, el que
tiene solución SÍ para todas las entradas y ProbNO, el que tiene solución NO para todas las
entradas. La demostración es la misma que hemos utilizado para ver que todos los problemas
de P (excepto estos dos) son polinómicamente equivalentes.
Respecto a la clase NP, es una pregunta con trampa: sólo los problemas de P pueden ser
P-Completos.

34. Sabemos que PAR ∈ P y SAT ∈ NP-Completo. Una reducción PAR ≤p SAT no nos aporta
más información sobre la complejidad de PAR y SAT. En cambio, una reducción SAT ≤p PAR
nos indicaría que SAT ∈ P y como SAT es NP-Completo podríamos concluir que P = NP.

35. Falso. La definición nos garantiza justamente lo contrario: que todo problema NP-Completo
es NP-Difícil.
CC-BY-NC-ND • PID_00267022 41 Complejidad computacional

Ejercicios de autoevaluación

1. Enunciad los problemas de cálculo SUMATORIO y AISLADOS (ejemplos 7 y 8) como pro-

blemas de decisión.

2. Enunciad los problemas de optimización CPP, LCS y MCP (ejemplos 9, 10 y 11) como
problemas de decisión.

3. Hemos encontrado en Internet una definición alternativa del problema de la suma de

subconjuntos (SUMA_SUB). La nueva definición es la siguiente:
SUMA_SUB_ALT: “Dado un conjunto de enteros C, decidir si algún subconjunto de C tiene
suma total igual a 0”

a) Describid los problemas de decisión SUMA_SUB y SUMA_SUB_ALT en forma de función.

b) Demostrad que el problema SUMA_SUB_ALT está en NP.

c) Describid una reducción polinómica SUMA_SUB_ALT ≤p SUMA_SUB.

d) Si SUMA_SUB es NP-Completo, la reducción anterior nos permite demostrar que el pro-

blema SUMA_SUB_ALT es NP-Difícil. ¿Cierto o falso?

4. Demostrad que el problema 3SAT pertenece a la clase NP.

5. Dados dos problemas A y B, justificad si son ciertas o falsas las afirmaciones siguientes:

a) Si A ≤p B y B ∈ P, entonces A ∈ P.

b) Si A ≤p B y A ∈ P, entonces B ∈ P.

c) Si A ≤p B y B ∈ NP, entonces A ∈ NP.

d) Si A ≤p B y A ∈ NP, entonces B ∈ NP.

e) Si A ≤p B y A es NP-Difícil, entonces B es NP-Difícil.

f) Si A ≤p B y A es NP-Completo, entonces B es NP-Completo.

g) Si A ≤p B y A es NP-Completo, entonces B es NP-Difícil.

h) Si S(A) ≤p B, donde S(A)• es un subconjunto de A• y A es NP-Difícil, entonces B es

NP-Difícil.

i) Si A ≤p S(B), donde S(B)• es un subconjunto de B• , y A es NP-Difícil, entonces B es

NP-Difícil.

6. Dado un número natural N, considerad el problema SUMA_N: “Calculad la suma de los N

primeros números naturales” (repasad el ejemplo 24).
a) Reformulad el problema SUMA_N como un problema de decisión.

b) Proponemos el algoritmo siguiente para resolver el problema SUMA_N: “sumamos conse-

cutivamente los números 1,2,3, . . . ,N – 1,N”. Calculad, en función de N, la complejidad
de este algoritmo. ¿Podemos afirmar que SUMA_N ∈ P?

c) Calculad, en función del número de bits necesarios para representar N, la complejidad del
algoritmo propuesto. ¿Podemos afirmar que SUMA_N ∈ NP?

d) ¿Podemos afirmar que SUMA_N ∈

/ P? Justificad la respuesta.

7. Considerad un conjunto finito X de N elementos. Queremos encontrar todas las funcio-

nes biyectivas de X en X*. *Repasad el apartado 1 sobre
funciones del módulo
“Conceptos previos: funciones y
a) Definimos el problema BIYECCIONES: “Listad todas las funciones biyectivas del conjunto
algoritmos”.
X”. Cada función biyectiva puede describirse mediante una lista de pares (valor, imagen)
para cada valor del dominio. ¿A qué clases de complejidad (tiempo y espacio) pertenece
este problema? ¿Puede pertenecer a la clase NP? Justificad las respuestas.
CC-BY-NC-ND • PID_00267022 42 Complejidad computacional

b) Considerad a continuación el problema NUMERO_BIYECCIONES: “Calculad el número

de funciones biyectivas del conjunto X”. ¿A qué clases de complejidad (tiempo y espacio)
pertenece este problema? ¿Es equivalente al anterior?

8. Actualmente, las relaciones entre las clases de complejidad P, NP y NP-C (NP-Completo)

no están claramente delimitadas. Para cada uno de los diagramas siguientes, indicad si el
escenario que se plantea es factible y si se está realizando alguna suposición actualmente no
demostrada sobre la relación entre estas 3 clases de complejidad.

a)

b)

c)
CC-BY-NC-ND • PID_00267022 43 Complejidad computacional

d)

e)

9. Algunos textos sobre complejidad computacional definen PARTICION sobre un multi-

conjunto de números naturales en lugar de un multiconjunto de números enteros. Es decir,
en el multiconjunto de números a particionar no se aceptan números negativos. Llamamos
PARTICION_NAT a esta versión del problema.

a) Describid una reducción polinómica PARTICION_NAT ≤p PARTICION.

b) Describid una reducción polinómica PARTICION ≤p PARTICION_NAT.

c) Indicad qué conclusiones se pueden extraer sobre la complejidad de PARTICION_NAT a

partir de los apartados anteriores.

10. El problema de la planificación de un multiprocesador (MPSCHED, multiprocessor schedu-

ling) estudia la asignación de un conjunto de tareas a un grupo de procesadores de forma que
su ejecución acabe antes de un tiempo límite. Formalmente, el problema se puede definir en
versión decisional de la forma siguiente:
Entrada: un conjunto finito A de tareas, una duración d(a) ∈ N para cada a ∈ A, un número
m ∈ N de procesadores y una fecha límite D ∈ N.
P existe una partición A = A1 ∪ A2 ∪ · · · ∪ Am de A en m conjuntos disjuntos tal que
Pregunta:
m« ax( a∈Ai d(a) | 1 ≤ i ≤ m) ≤ D?

a) Indicad si MPSCHED se puede verificar en tiempo polinómico.

b) Partiendo del problema de decisión PARTICION_NAT definido en el ejercicio anterior,

proponed una reducción polinómica PARTICION_NAT ≤p MPSCHED (Indicación: con-
siderad m = 2).

c) ¿Sería posible hacer la reducción PARTICION ≤p MPSCHED, llegando a utilizar PARTICION

en lugar de PARTICION_NAT? (Indicación: centraos en la diferencia entre PARTICION y
PARTICION_NAT).

d) Indicad qué conclusiones se pueden extraer de los apartados anteriores sobre la compleji-
dad del problema MPSCHED.
CC-BY-NC-ND • PID_00267022 44 Complejidad computacional

Solucionario

1. SUMATORIO: “Dada una secuencia finita de enteros E y un entero k, decidir si k =

P
x∈E x.”
AISLADOS: “Dado un grafo G = (V,A) y un conjunto de vértices V ′ , decidir si el conjunto de
vértices de grado 0 de V es igual a V ′ .”

2. CPP: “Dado un conjunto de puntos en un espacio bidimensional, donde cada punto está
definido por unas coordenadas (x,y), y un número real d, decidir si hay algún par de puntos
que estén a distancia d o inferior.”
LCS: “Dadas dos cadenas de caracteres a y b y un entero k, decidir si la subcadena común
más larga entre a y b tiene k caracteres o más.”
MSP: “Dado un grafo ponderado y conexo (G,w) y un número real k, decidir si el árbol
generador minimal tiene peso k o menos.”

3. a) SUMA_SUB : 2Z × Z → {SÍ, NO}

SUMA_SUB_ALT : 2Z → {SÍ, NO}

b) La entrada del problema es un conjunto C. Un testigo sería un subconjunto C′ ⊆ C,

concretamente el subconjunto con suma 0.

A partir del conjunto de entrada y el testigo, es posible validar que todos los elementos
de C′ estaban en el conjunto original C y que la suma de todos los elementos de C′ es
igual a 0. Todo esto se puede comprobar en tiempo polinómico.

También es directo ver que si SUMA_SUB_ALT(C) = NO, cualquier subconjunto que

propongamos como testigo no pasará la validación al no tener una suma total igual a 0
(si hubiera alguno, la respuesta al problema sería SÍ).

c) La reducción SUMA_SUB_ALT ≤p SUMA_SUB es bastante directa: usamos como función

de reducción f (C) = (C,0). Esta reducción fija como valor objetivo t = 0 sin modificar el
conjunto C. Entonces SUMA_SUB_ALT(C) = SUMA_SUB(C,0) para cualquier C, indepen-
dientemente de si el resultado es SÍ o NO. La función f es calculable en tiempo polinómi-
co y, por lo tanto, queda demostrado que la reducción SUMA_SUB_ALT ≤p SUMA_SUB
es posible.

d) Falso. La reducción que permitiría llegar a esta conclusión es

SUMA_SUB ≤p SUMA_SUB_ALT.

4. Para demostrar que 3SAT ∈ NP tenemos que justificar que 3SAT se puede verificar en tiem-
po polinómico. En el ejemplo 29, ya hemos visto que hay un procedimiento para verificar
SAT en tiempo polinómico. Dado que 3SAT es un caso particular de SAT, el procedimiento
del ejemplo 29 también nos permite verificar 3SAT en tiempo polinómico.

5. Justificamos cada afirmación:

a) Cierta, por las propiedades de las reducciones polinómicas.

b) Falsa. La reducción no nos aporta ninguna información sobre la complejidad de B.

c) Cierta, por las propiedades de las reducciones.

d) Falsa. La reducción no nos aporta ninguna información sobre la complejidad de B.

e) Cierta. Si A es NP-Difícil, entonces C ≤p A para todo C ∈ NP. Por la propiedad de transiti-

vidad, C ≤p B para todo C ∈ NP y esto quiere decir que B es NP-Difícil.

f) Falsa. Si A es NP-Completo, entonces C ≤p A para todo C ∈ NP y A ∈ NP. Por la propiedad

de transitividad, C ≤p B para todo C ∈ NP, pero no podemos afirmar que B ∈ NP.

g) Cierta. Si A es NP-Completo, entonces C ≤p A para todo C ∈ NP y A ∈ NP. Por la propie-

dad de transitividad, C ≤p B para todo C ∈ NP y esto quiere decir que B es NP-Difícil.

h) Falsa. Un subconjunto de un problema NP-Difícil puede no ser NP-Difícil. Por ejemplo,

podríamos elegir S(A) = ProbNO, que no es NP-Difícil (recordemos que los problemas
con alguna entrada con solución SÍ no se pueden reducir a este problema y, por lo tanto,
no es posible que todos los problemas de NP se puedan reducir a él). Por lo tanto, la
CC-BY-NC-ND • PID_00267022 45 Complejidad computacional

reducción ProbNO ≤p B no nos aporta suficiente información para asegurar que B es

NP-Difícil.

i) Falsa. Aunque un problema S(B) sea NP-Difícil, esto no significa que los problemas B que
lo incluyen (S(B)• ⊆ B• ) sean NP-Difíciles. Por ejemplo, podríamos escoger B = ProbSI,
que sabemos que no es NP-Difícil (los problemas que tienen alguna entrada con solución
NO no se pueden reducir a este problema).

6. a) El problema
P de decisión asociado sería, SUMA_N: “Dado un natural N y un natural k,
decidir si Ni=1 i = k”.

b) En el algoritmo propuesto tenemos que hacer N –1 sumas por lo cual tendrá una compleji-
dad O(N), en función de N. Aunque la complejidad que hemos calculado es polinómica,
no podemos afirmar que SUMA_N ∈ P dado que no hemos tenido en cuenta el tamaño
de la entrada del algoritmo.

c) El número de bits necesarios para representar N es ⌊log2 N⌋ + 1. La complejidad será ahora

O(2n ). Con la información que hemos obtenido, podemos afirmar que SUMA_N ∈ .

Para decidir si SUMA_N ∈ NP tenemos que ver si el problema de decisión SUMA_N es

verificable
PN en tiempo polinómico, es decir, si podemos verificar en tiempo polinómico
que i=1 i = k donde k es el valor de la suma de los N primeros números naturales.
Como función verificadora no podemos elegir el algoritmo propuesto dado que tiene
una complejidad exponencial en función del tamaño de la entrada.

PN N(N+1)
Por suerte, la fórmula de Euler i=1 i = 2
se puede utilizar como función verificado-
ra, v : N × N → {SÍ,NO} definida por, si SUMA_N = k entonces v(N,k) = SÍ si N(N+1)
2
=ky
v(N,k) = NO, en otro caso. Esta función verificadora tiene una complejidad polinómica
y, por lo tanto, podemos concluir que SUMA_N ∈ NP.

d) Para poder afirmar que SUMA_N ∈ / P tendríamos que estar seguros de que no hay ningún
algoritmo de complejidad polinómica para calcular la suma de los N primeros núme-
ros naturales. Pero en el apartado anterior hemos visto que la fórmula de Euler resuel-
ve el problema con una complejidad polinómica. Por lo tanto, podemos afirmar que
SUMA_N ∈ P.

Observad que la fórmula de Euler sirve al mismo tiempo para demostrar que SUMA_N ∈
P y también como función verificadora (revisad el ejercicio 18).

7. El número de funciones biyectivas de un conjunto finito X de N elementos coincide con

el número de N-muestras ordenadas sin repetición de elementos de X que coincide con el
número de permutaciones P(N) de los elementos de X*. Así, el número de permutaciones es
P(N) = N!. *Proposición 4 del módulo
“Conceptos previos: funciones y
algoritmos”.
a) La solución al problema BIYECCIONES consistirá en dar las N! muestras ordenadas sin
repetición de N elementos de X. Como en el ejemplo 27, la salida de este problema
tendrá un tamaño exponencial respecto a la entrada, concretamente, N! veces el tamaño
de la entrada. Así pues, este problema pertenece a y a EXPSPACE pero no a P ni a
PSPACE.

Como BIYECCIONES ∈/ PSPACE y NP ⊆ PSPACE, podemos afirmar como conclusión que

BIYECCIONES ∈
/ NP.

b) La solución al problema NUMERO_BIYECCIONES consistirá en calcular N!. La diferencia

con el apartado anterior es que no es necesario dar todas las permutaciones, sino sólo
saber cuántas hay.

Calcular N! requiere N – 1 multiplicaciones y, por lo tanto, se puede calcular en tiem-

po lineal. Esto quiere decir que NUMERO_BIYECCIONES ∈ P y como consecuencia
NUMERO_BIYECCIONES ∈ PSPACE. Como conclusión, NUMERO_BIYECCIONES no es
equivalente a BIYECCIONES.

Fijémonos que en este problema la entrada no es un valor del que tenemos que medir
su longitud en representación binaria, sino un conjunto de N elementos y, por lo tanto,
el tamaño de la entrada es N (el número de elementos del conjunto). Para poner un
ejemplo de esta diferencia, no es lo mismo un problema donde la entrada es un conjunto
CC-BY-NC-ND • PID_00267022 46 Complejidad computacional

de 75000 números que otro problema donde la entrada es el valor “75000”: en el primer
caso, el tamaño de la entrada es 75000, mientras que en el segundo caso el tamaño es
⌊log2 75000⌋ + 1 = 17.

8. En la situación actual del conocimiento, P, NP-C son subconjuntos de NP.

a) Factible, pero asume que P = NP.

b) No factible. Si P = NP, entonces P = NP = NP-C. Por lo tanto, esta situación no puede

suceder.

c) Factible, pero asume que P 6= NP y P 6= NP-C.

d) Factible, pero en este diagrama se supone que hay problemas que están al mismo tiempo
en P y en NP-C. Por la definición de NP-C, entonces estamos asumiendo que P = NP = NP-
C.

e) Factible, pero asume que P 6= NP y P 6= NP-C.

9. a) La reducción PARTICION_NAT ≤p PARTICION es directa, utilizando como función

de reducción f (x) = x, la función identidad. Es decir, como todo número natural es
también un número entero, toda entrada de PARTICION_NAT es una entrada correcta
de PARTICION. La solución calculada por PARTICION para esta entrada será igual a la de
PARTICION_NAT.

b) La reducción PARTICION ≤p PARTICION_NAT es más interesante: partiendo de un mul-

ticonjunto de enteros que puede contener números negativos, tenemos que construir
un multiconjunto de números naturales que preserve la solución. La función de reduc-
ción que utilizaremos será g(C) donde g(C) contiene el multiconjunto resultante de apli-
car la función “valor absoluto” a cada elemento de C. Es decir, para C = [2,4,0, – 4],
g(C) = [2,4,0,4].

Esta función se puede calcular en tiempo polinómico: sólo es necesario hacer un recorri-
do del multiconjunto, cambiando el signo a los valores negativos.

Nos queda demostrar que PARTICION(C) = PARTICION_NAT(g(C)), tanto para los casos
donde PARTICION(C) = SÍ como cuando PARTICION(C) = NO. Procedemos a hacerlo a
continuación:

• Caso PARTICION(C) = SÍ: En este

P caso, tenemos
P una partición de C en dos multicon-
juntos C1 y C2 de forma que x∈C1 x = x∈C2 x. Veremos que es posible construir
una partición equivalente en g(C) obteniendo C′1 y C′2 .

La idea es la siguiente: si no hay números negativos en C, entonces g(C) = C y la

misma partición nos sirve para g(C) (C′1 = C1 ,C′2 = C2 ). Si no, construimos C′1 y C′2 de
la forma siguiente: todos los valores no negativos de C1 van a C′1 y todos los valores
no negativos de C2 van a C′2 ; si hay algún valor negativo en C1 , su valor absoluto pasa
a C′2 y viceversa. Por ejemplo, si C1 = [7, – 1,0,2,2] y C2 = [8,4,6, – 3, – 5] tendríamos
que C′1 = [7,0,2,2,3,5] y C′2 = [8,4,6,1]. Intuitivamente, es lo mismo sumar –x a C1
que sumar +x a C2 , de forma que esta transformación preserva la suma total de los
elementos de la partición.

• Caso PARTICION(C) = NO: Si no hay ninguna partición en C donde la suma total

de cada parte sea igual, tenemos que demostrar que tampoco hay ninguna en g(C).
Haremos la demostración por reducción al absurdo: supondremos que hay una par-
tición para g(C) cuando PARTICION(C) = NO y llegaremos a una contradicción.

Supongamos que hay una partición para g(C) en dos multiconjuntos C′1 y C′2 con la
misma suma total. A partir de aquí, construiremos una partición de C en C1 y C2 que
también tiene la misma suma total. La partición se construye de forma equivalente
al apartado anterior: para cada x ∈ C, si abs(x) estaba en C′1 , entonces lo añadimos a
C1 si x ≥ 0 y a C2 si x < 0; similarmente, si abs(x) estaba en C′2 , entonces lo añadimos
a C2 si x ≥ 0 y a C1 si x < 0.
CC-BY-NC-ND • PID_00267022 47 Complejidad computacional

Esta partición C1 y C2 preserva la suma total de cada parte, por el mismo razonamien-
to utilizado previamente:
Psumar –xP a una parte o sumar +x a la otra
Pson equivalentes.
P
Esto quiere decir que si x∈C′ x = x∈C′ x, también se cumplirá x∈C1 x = x∈C2 x.
1 2

La existencia de la partición C1 y C2 indica que PARTICION(C) = SÍ, contradiciendo

nuestra hipótesis. Esto nos permite concluir que la hipótesis de que hay una partición
para g(C) cuando PARTICION(C) = NO es incorrecta, es decir, que si PARTICION(C)
= NO entonces PARTICION_NAT(g(C)) = NO.

c) La reducción PARTICION_NAT ≤p PARTICION y el hecho que PARTICION sea NP indica

que PARTICION_NAT pertenece a NP. La reducción PARTICION ≤p PARTICION_NAT y
el hecho que PARTICION sea NP-Difícil nos indica que el problema PARTICION_NAT es
también un problema NP-Difícil. Considerando las dos reducciones al mismo tiempo,
podemos concluir que PARTICION y PARTICION_NAT son polinómicamente equivalen-
tes (por la existencia de las dos reducciones) y que PARTICION_NAT es un problema
NP-Completo (al ser NP y NP-Difícil).

10. a) Empezamos proponiendo un testigo para MPSCHED: una partición del conjunto A
en m conjuntos disjuntos.

La función de verificación consiste en sumar, para cada procesador j, la duración d(a) de

las tareas asignadas a j y comparar cada duración total con la fecha límite D. Una entrada
se considera verificada si el testigo consigue que, en cada procesador, la duración total
sea inferior a D.

Si hay n tareas y m procesadores, para este cálculo tendremos que hacer n – m sumas y
m comparaciones. Esto significa que la función de verificación es calculable en tiempo
polinómico.

Si la solución de MPSCHED es SÍ, habrá algún testigo que nos permita verificar esta so-
lución (por la propia definición del problema, que nos pide que exista esta partición).
Claramente, si la solución para una entrada es NO, ningún testigo nos permitirá verifi-
carla.

b) La reducción f (x) ha de partir de una entrada del problema PARTICION_NAT y construir

una entrada equivalente del problema MPSCHED. Es decir, que partiendo de un multi-
conjunto de naturales, tenemos que llegar a un conjunto de tareas, una duración para
cada tarea, un número de procesadores y una fecha límite.

Intuitivamente, dado que PARTICION_NAT intenta dividir un multiconjunto en dos par-

tes, tendríamos que plantejar un problema de MPSCHED con m = 2 procesadores. La
duración de cada tarea debería estar relacionada con el valor de los enteros originales, y
la fecha límite, con la suma total de los números naturales.

Concretamente, la propuesta de función de reducción f (C) es: hay una tarea para cada
número x de C, conP duración d igual a x y D es la mitad de la suma total de los valores de
C, es decir, D = ( x∈C x)/2. Esta función de reducción se puede calcular en tiempo poli-
nómico: sólo es necesario hacer un recorrido de C, calcular la suma total de los valores y
hacer una división por 2.

Podemos demostrar la equivalencia entre las entradas de PARTICION_NAT y MPSCHED

según esta reducción. La duración total de las tareas es 2D y, por lo tanto, sólo se pue-
de conseguir que ambos procesadores completen el cálculo antes de la fecha límite D
repartiendo las tareas de forma perfectamente equilibrada entre los procesadores (dura-
ción total D en cada procesador). Si no es así, uno de los procesadores tardaría menos de
D y el otro tardaría más, incumpliendo la fecha límite. Esto es equivalente a conseguir
particionar un conjunto de números naturales en dos partes con la misma suma total. Es
decir, PARTICION_NAT(C) = MPSCHED(f (C)).

c) La reducción desde PARTICION es posible, pero no se puede utilizar la misma función de

reducción que se utiliza para PARTICION_NAT ≤p MPSCHED. En concreto, haría falta
definir el mapeo para los números negativos del multiconjunto C, teniendo en cuenta
que las duraciones de las tareas no pueden ser negativas. Por esto nos hemos basado en
PARTICION_NAT en lugar de PARTICION para hacer la reducción.

La forma más sencilla de definir una función de reducción PARTICION ≤p MPSCHED

podría hacerse básicamente componiendo la función que reduce
CC-BY-NC-ND • PID_00267022 48 Complejidad computacional

PARTICION ≤p PARTICION_NAT (g, definida en un ejercicio de autoevaluación previo)

con la que reduce PARTICION_NAT ≤p MPSCHED (f , definida en el apartado anterior).
La función de reducción h para PARTICION ≤p MPSCHED se definiría como h(C) =
f (g(C)).

d) A partir del apartado a, podemos decir que MPSCHED pertenece a NP. A partir del apar-
tado b, podemos decir que MPSCHED es NP-Difícil. Combinando ambas informaciones,
podemos decir que MPSCHED es NP-Completo.
CC-BY-NC-ND • PID_00267022 49 Complejidad computacional

Bibliografía

Cook, S. (2003). The Importance of the P versus NP Question. [s.l.]: Journal of the ACM (vol. 1,
núm. 50, págs. 27-29)

Garey, M. R.; Johnson, D. S. (1979). Computers and Intractability. A Guide to the Theory of
NP-Completeness. Nueva York: Freeman and Co.

Papadimitriou, C. H. (1994). Computational Complexity. Reading (Massachusetts): Addison

Wesley.