Tema 2

Optimización II

Clases de problemas P y
NP
 Índice
Esquema 3

Ideas clave 4
© Universidad Internacional de La Rioja (UNIR)

2.1. Introducción y objetivos 4

2.2. Notación asintótica 5
2.3. Significado de 𝑶(𝒕) 9
2.4. Complejidad computacional 16
2.5. Cuaderno de ejercicios 23
2.6. Referencias bibliográficas 31
 © Universidad Internacional de La Rioja (UNIR)

Tema 2. Esquema
Optimización II
Esquema

3
 Ideas clave

2.1. Introducción y objetivos

Al formular problemas de optimización, pensar en la complejidad computacional es

natural. Esto se da con la finalidad de determinar, en principio, la necesidad de los
recursos computacionales que hagan falta para darle solución a problemas
específicos. Estos recursos, entre otras cosas, suelen incluir tiempo de ejecución, o
bien la cantidad de operaciones o pasos requeridos para resolver el problema y el
espacio, es decir, la cantidad de memoria utilizada para tales fines.

El estudio de la complejidad computacional resulta fundamental en la informática, ya

que nos ayuda a comprender cuándo un problema es difícil de resolver y, en este
sentido, cuándo es posible diseñar algoritmos para resolverlo de manera eficiente.
Este aspecto importante redunda en áreas muy específicas, como la criptografía,
donde la seguridad de los sistemas y la ciberseguridad se basan en la dificultad de
resolver ciertos problemas.

Establecer una clasificación resulta imperante. En efecto, las clases de complejidad

agrupan problemas según la cantidad de recursos necesarios para resolverlos.
Algunas de las clases de complejidad más comunes incluyen P, NP, NP-completo,
PSPACE y EXP. Cada una de estas clases representa un conjunto de problemas con
características particulares en términos de su dificultad computacional.

El objetivo principal de este tema es que se comprendan y afiancen los siguientes

puntos:

 Establecer y reconocer una clasificación clara de los diferentes problemas a

enfrentar.
 Establecer la diferencia entre problemas determinísticos y no determinísticos.

Optimización II
4
Tema 2. Ideas clave
 Diferenciar de manera clara un problema P y un problema NP.
 Comprender la notación usada para la clasificación.
 Comprender la implicación de este tipo de clasificación en los métodos a utilizar.

2.2. Notación asintótica

En ciencias de la computación se usa la notación asintótica para tener una

aproximación de la complejidad temporal o espacial de un algoritmo. De esta manera
nos podemos hacer una idea de la eficiencia de los programas, pero en realidad a qué
nos referimos cuándo hablamos de ella.

Definición de notación asintótica: la notación asintótica es una notación que

se usa para representar matemáticamente el comportamiento de una función
y así poder, entre otras cosas, determinar un orden para clasificar los distintos
tipos de algoritmos a utilizar.

El tiempo de ejecución lo deberemos expresar mediante una fórmula o función

matemática y, en este sentido, es importante saber qué argumentos debe tomar
dicha función. Consideremos la siguiente función para una explicación informal:

Optimización II
5
Tema 2. Ideas clave
 Figura 1. Gráfica de 𝑇(𝑛) = 𝑛 + 5𝑛 + 10, 𝑛 ≥ 0. Fuente: elaboración propia.

Procedamos a descomponer esta función y, a partir de allí, determinar su orden.

Figura 2. Gráficas separadas para comparación. Fuente: elaboración propia.

Optimización II
6
Tema 2. Ideas clave
Observemos que:

 El término de mayor relevancia es 𝑛 , por ser el de mayor orden.

• Nota: puede que existan varios términos si la función depende de varios
parámetros.

 Para valores pequeños de 𝑛, todos los términos influyen.

 Mediante la notación asintótica vamos a simplificar y, así, aislar dichos términos

que más influyen cuando 𝑛 toma valores muy grandes.

En general, la representación matemática determina el comportamiento de una

función, pero las necesitamos para tener una aproximación de la complejidad
temporal o espacial de un algoritmo. En este sentido, estas medidas están dadas por:

 Complejidad temporal: es la cantidad de operaciones que se realizan en un

algoritmo para resolver un problema.

 Complejidad espacial: es la cantidad de operaciones que se realizan en un

algoritmo para resolver un problema, pero en una dimensión dada.

Los siguientes cuatro principios forman parte de los muchos principios que
determinan el desempeño de un algoritmo. Veamos:

 Secuencia de acciones: representa la suma de los costos de cada acción que se

realiza en un algoritmo.

 Alternación: corresponde al caso cuando existen múltiples opciones y se debe

determinar cuántas veces se efectúa cada alternativa.

 Ciclos: los ciclos evalúan la cantidad de veces que se repite determinada acción.

Optimización II
7
Tema 2. Ideas clave
 Llamadas a procesos: el costo de una llamada a un cuerpo (proceso, método o
función) que se realiza en un algoritmo.

Cuando hablamos de comportamiento asintótico, hacemos referencia a dicho

comportamiento cuando 𝑛 → ∞, donde 𝑛 es el tamaño del problema. En este
sentido, podremos hablar de tres tipos básicos de comportamiento asintótico, o bien
tres notaciones básicas:

 𝒇 ~ 𝒈 ∶ refiere a cuando 𝑓 y 𝑔 son asintóticamente equivalentes. En efecto,

( )
𝑓 ~ 𝑔 significa que lim ( )
= 1. En efecto, 5𝑥 + 3𝑥 − 2 ~ 5𝑥 , es decir, para 𝑛
→

muy grande son muy parecidas. Además, se puede mostrar que la relación "~" es
una relación de equivalencia. Entonces, la idea básica consiste en tomar en cuenta
solo los términos principales, ignorando aquellos que crecen más lento.

 𝒇 ≼ 𝒈: refiere a cuando 𝑓 está asintóticamente dominada por 𝑔. A saber, 𝑓 ≼ 𝑔

( ) ( )
significa que lim sup ( )
< ∞. Es decir, el cociente ( )
está eventualmente
→

acotado por un valor finito. La idea básica es notar que 𝑓 crece más lento que 𝑔 o,
en su defecto, tan rápido como 𝑔.

 𝒇 ≍ 𝒈∶ refiere a cuando 𝑓 y 𝑔 son respectivamente acotadas, es decir, cuando

( )
hay constantes positivas 𝑐 y 𝑐 , tales que 𝑓 ≍ 𝑔 significa que 𝑐 ≤ ( )
≤ 𝑐 , con

𝑛 suficientemente grande. Claramente, 𝑥 ≍ 2𝑥, o bien 𝑥 ≍ (2 + sen 𝜋𝑥)𝑥. La

relación " ≍ " es de equivalencia.

Optimización II
8
Tema 2. Ideas clave
2.3. Significado de 𝑶(𝒕)

En el marco de establecer el costo computacional, la notación 𝑂(𝑡) es de uso habitual

en matemática y tiene un significado específico. Según Trefethen y Bau III (1997), el
significado de 𝑂(𝑡) está dado por la siguiente definición:

Definición 𝑂(𝑡): dadas dos funciones, 𝜙, 𝜓, con valores reales, la igualdad

𝜑(𝑡) = 𝑂 𝜓(𝑡) [1] indica que existe una constante 𝐶 tal que, para todo 𝑡
suficientemente cercano a un valor límite 𝑡 (por ejemplo, 𝑡 → 0, 𝑡 → ∞,,
etc.), se tiene |𝜑(𝑡)| ≤ 𝐶|𝜓(𝑡)| [2].

En virtud de la necesidad de tener un símbolo matemático para establecer el orden,

consideremos 𝑓: ℕ ⟶ ℝ ∪ {0} una función arbitraria. Indicaremos como 𝑂(𝑓(𝑛)) al
conjunto de todas las funciones 𝑇: ℕ ⟶ ℝ ∪ {0}, tales que existe 𝑐 ∈ ℝ , donde
𝑇(𝑛) ≤ 𝑐 ∙ 𝑓(𝑛) para todo 𝑛 ≥ 𝑛 (umbral). En símbolos:

𝑂 𝑓(𝑛) ≡ {𝑇: ℕ ⟶ ℝ ∪ {0} | 𝑇(𝑛) ≤ 𝑐 ∙ 𝑓(𝑛), para algún 𝑐 ∈ ℝ }

Para todo 𝑛 ≥ 𝑛 :

Figura 3. Acotamiento y umbral. Fuente: elaboración propia.

Optimización II
9
Tema 2. Ideas clave
En este caso, diremos que « 𝑇(𝑛) es de orden 𝑓(𝑛)», o bien que «𝑇(𝑛) no crece más
rápido que 𝑓(𝑛)».

Como ejemplo, recordemos la relación:

sen 𝑡
≤1
𝑡

Que podemos observarla en la Figura 4 (a):

sen2 𝑡
Figura 4. (a) Gráfica de la función – (b) Gráficos de las funciones 𝜑(𝑡) = sen (𝑡) (azul) y 𝜓(𝑡) = 𝑡
𝑡2
(verde). Fuente: Lloyd N. Trefethen and David Bau III (1997)

Esto nos permite afirmar que sen 𝑡 ≤ 𝑡 cuando 𝑡 → 0. De esta manera, |sen (𝑡)| =
sen (𝑡) ≤ 𝐶 𝑡 , con 𝐶 = 1 [3] y diremos que 𝜑(𝑡) = 𝑂(𝜓(𝑡)) cuando 𝑡 → 0.
Particularmente si 𝜙(𝑡)/𝜓(𝑡) = 1 para 𝑡 → 𝑡 (como en el caso analizado), decimos
que 𝜑(𝑡) tiende asintóticamente a 𝜓(𝑡), lo que significa que, en ese límite, ambas
funciones son prácticamente indistinguibles, como podemos observar en la Figura 4
(b) y 𝜑(𝑡) tiende asintóticamente a 𝑡 .

Optimización II
10
Tema 2. Ideas clave
Cantidad de operaciones

Cuando contamos con un algoritmo que permite resolver algún problema de cálculo,
es importante tener conocimiento de cuál es su costo de cálculo, es decir, cuál es el
número de operaciones que deberán realizarse para completarlo y obtener el
resultado que estamos buscando. Esto permite calificar el algoritmo y comparar su
eficiencia con respecto a otro que resuelva el mismo problema.

En un ordenador, los cálculos matemáticos se reducen a un conjunto de operaciones

aritméticas elementales denominadas operaciones de punto flotante, o bien flops.
Estas operaciones son las de suma, resta, multiplicación y división.

La aritmética de punto flotante está basada en una representación de punto flotante

del conjunto de números reales. En un sistema numérico de punto flotante, la
posición del punto decimal (o binario) se almacena separadamente de los dígitos y la
precisión con que puede representarse un número es proporcional al valor del propio
número. Esto lo distingue de una representación de punto fijo, donde la precisión es
constante.

Tomemos como ejemplo un polinomio genérico de grado 2:

𝑝(𝑡) = 𝑎 + 𝑎 𝑡 + 𝑎 𝑡

Para este, es necesario conocer el número de operaciones necesarias para evaluar

dicho polinomio en 𝑡 = 𝑡 , esto es, cuántas operaciones elementales deben
realizarse para conocer el valor que toma 𝑝(𝑡) cuando 𝑡 = 𝑡 :

𝑝(𝑡 ) = 𝑎 + 𝑎 𝑡 + 𝑎 𝑡 [4]

Optimización II
11
Tema 2. Ideas clave
En el primer término, no es necesaria ninguna operación, ya que 𝑎 es conocido. En
el segundo término, debemos resolver el producto 𝑎 𝑡 , lo que implica una operación
elemental. El valor del último término se encuentra luego de realizar dos productos,
uno para hallar el valor de 𝑡 = 𝑡 ∙ 𝑡 y luego uno más para hallar 𝑎 𝑡 .

Finalmente, debemos sumar los tres términos, lo que agrega dos operaciones de
suma al cálculo. En resumen, tenemos tres productos y dos sumas, lo que da un total
de cinco flops para la evaluación del polinomio. Ahora bien, la expresión [4] no tiene
una única representación, es decir, existen diversas maneras de escribir al polinomio
𝑝(𝑡). Un ejemplo de ello podría ser:

𝑝(𝑡 ) = 𝑎 + 𝑡 (𝑎 + 𝑎 𝑡 )

En este formato, el número de flops necesarios para su evaluación se reduce a cuatro,

es decir, dos productos y dos sumas. Aunque esto no parece un ahorro de cálculo
muy importante, sí es relevante en un caso más general.

Caso general

Consideremos el polinomio de grado 𝑛 dado por:

𝑝(𝑡) = 𝑎 + 𝑎 𝑡 + 𝑎 𝑡 + 𝑎 𝑡 + ⋯ + 𝑎 𝑡 +𝑎 𝑡 [5]

Para evaluar a este polinomio en 𝑡 = 𝑡 , es necesario resolver:

 Ninguna operación en el primer término.

 Un producto en el segundo término 𝑎 ∙ 𝑡 .
 Dos productos en el tercer término, 𝑎 ∙ 𝑡 ∙ 𝑡 .
 Tres productos en el cuarto término, 𝑎 ∙ 𝑡 ∙ 𝑡 ∙ 𝑡 , y así sucesivamente.
 Para el penúltimo término, se tiene que: 𝑎 ∙𝑡 =𝑎 ∙𝑡 ∙𝑡 ∙⋯∙𝑡 ⟶
productos

𝑛 − 1 productos.

Optimización II
12
Tema 2. Ideas clave
 Para el último término: 𝑎 ∙ 𝑡 , claramente se generan 𝑛 productos.

Para calcular el total de operaciones realizadas, nos queda:

𝑛(𝑛 + 1)
0 +1+2 +3+⋯+𝑛 = 𝑖= 𝑖= (Fórmula de Gauss)
2

Finalmente, debemos sumar los 𝑛 + 1 términos de la expresión [5], lo que implica

realizar 𝑛 sumas. Entonces, el número de flops requeridas para evaluar un polinomio

de grado 𝑛 escrito en su forma canónica es 𝜑(𝑛) = (𝑛 + 3) = 𝑛 + 𝑛 ∼ . Es

habitual, al indicar el número de operaciones de un algoritmo, despreciar los

términos de menor orden (como hicimos en este caso), ya que estos suelen no ser
significativos a menos que 𝑛 sea pequeño.

Por otra parte, podemos utilizar la notación "𝑂" para calificar el costo de cálculo.
Vemos que si 𝑛 > 2, esta expresión es menor a 2𝑛 y, por lo tanto, diremos que el
algoritmo es 𝑂(𝑛 ). Más todavía:

𝜑(𝑛) 3
lim = lim 1 + = 1
→ 𝑛 ⁄2 → 𝑛

Ambas funciones tienden asintóticamente al mismo valor, lo que justifica el no tener

en cuenta el término 𝑛 para 𝑛 grande.

En este sentido, diremos que todos los algoritmos que sean 𝑂(𝑛) son comparables
respecto de su costo de cálculo. Todos los que sean 𝑂(𝑛 ) son comparables entre sí
y, así en general, todos los algoritmos 𝑂(𝑛 ) tendrán una eficiencia computacional
similar.

Optimización II
13
Tema 2. Ideas clave
Figura 5. Número de operaciones empleadas en la evaluación de un polinomio de grado 𝑛 escrito en la forma
canónica (puntos azules) y en la forma de Horner (puntos rosas). Fuente: elaboración propia.

El algoritmo de Horner es un algoritmo para evaluar de forma eficiente una

evaluación polinómica cuando estamos hablando de su forma monomial, es decir,
bajo la localización de un extremo local. En consecuencia, si se tiene el polinomio:
𝑝(𝑡) = 𝑎 + 𝑎 𝑡 + 𝑎 𝑡 + 𝑎 𝑡 + ⋯ + 𝑎 𝑡 + 𝑎 𝑡 , donde 𝑎 , 𝑎 , … , 𝑎 son
números reales, queremos evaluar el polinomio a un valor específico de 𝑡 . Para
llevar a cabo el procedimiento, definimos una nueva sucesión de constantes de la
forma:

𝑏 ≔ 𝑎
𝑏 ≔ 𝑎 +𝑏 𝑡
⋮ ⋮ ⋮
𝑏 ≔ 𝑎 +𝑏 𝑡

Donde 𝑏 = 𝑝(𝑡 ). Ahora bien, la forma en que esta sucesión de constantes trabaja
es la siguiente, si consideramos la reescritura del polinomio anterior:

𝑝(𝑡) = 𝑎 + 𝑡 𝑎 + 𝑡 𝑎 + ⋯ + 𝑡(𝑎 + 𝑎 𝑡)

Optimización II
14
Tema 2. Ideas clave
De donde se obtiene finalmente:

𝑝(𝑡 ) = 𝑎 + 𝑡 𝑎 + 𝑡 𝑎 + ⋯ + 𝑡 (𝑎 +𝑏 𝑡 )
= 𝑎 + 𝑡 𝑎 + 𝑡 (𝑎 + ⋯ + 𝑡 (𝑏 )⋯)
⋮ ⋮
= 𝑎 +𝑡 𝑏
= 𝑏

Esta expresión requiere de 𝑛 productos y 𝑛 sumas para su evaluación, por tanto, el

número de operaciones requeridas para su evaluación es 2𝑛. Este algoritmo es 𝑂(𝑛),
un orden menor al caso anterior y, por lo tanto, su costo computacional también lo
es.

En la Figura 5 se graficaron ambos casos, la cantidad de flops necesarias en función

del grado del polinomio. Claramente, podemos ver cuánto más eficiente es la forma
de Horner al momento de evaluar un polinomio.

Por último, aunque no nos enfoquemos en este punto, debemos tener presente que
en el costo computacional de un algoritmo hay mucho más que el número de
operaciones que este requiere. Por ejemplo, en una computadora que cuente con un
único procesador, el tiempo de ejecución está afectado por el movimiento de los
datos entre distintos componentes de la memoria y por otros trabajos que estén
ejecutándose al mismo tiempo. En una máquina con un procesador múltiple, también
hay que tener en cuenta el tiempo empleado en la comunicación entre procesadores.

Optimización II
15
Tema 2. Ideas clave
2.4. Complejidad computacional

La complejidad computacional se enfoca directamente en el estudio de la cantidad

de recursos computacionales necesarios para resolver problemas específicos. Estos
recursos suelen incluir el tiempo o cantidad de operaciones requeridas para resolver
un problema y el espacio, o bien la cantidad de memoria utilizada en el proceso.

La complejidad computacional se divide en clases deterministas (P) y no

deterministas (NP). Los problemas en P son aquellos que se pueden resolver
eficientemente en tiempo polinomial, mientras que NP se refiere a problemas que se
pueden verificar en tiempo polinomial (aunque aún no se ha demostrado si pueden
resolverse en tiempo polinomial).

La complejidad computacional es fundamental en la informática, ya que nos ayuda a

comprender cuándo un problema es difícil de resolver y cuándo es posible diseñar
algoritmos eficientes para resolverlo. También tiene aplicaciones en áreas como la
criptografía, donde la seguridad de los sistemas se basa en la dificultad de resolver
ciertos problemas.

Figura 6. Clasificación de complejidad computacional. Fuente: elaboración propia.

Un ejemplo claro de la diferencia entre P y NP, a priori, puede ser el siguiente:

resolver una raíz cuadrada (para lo que existe un método muy laborioso) es más
complicado o lento que la operación inversa.

Optimización II
16
Tema 2. Ideas clave
Si un problema nos pide que comprobemos si un número determinado 𝑥 es la raíz
cuadrada de 𝑦, podríamos resolverlo de dos formas:

 Calculando la raíz de 𝑦 y comparando con 𝑥 (resolución → proceso lento y

engorroso).

 O bien, elevando al cuadrado a 𝑥 y comparando con 𝑦 (verificación → por simple

multiplicación 𝑥 ∙ 𝑥).

La conclusión que sacamos de este sencillo ejemplo es que, en algunos problemas,

comprobar la solución es más eficiente que calcularla. La complejidad de la función
«elevar al cuadrado» es más simple que calcular la raíz cuadrada.

P es la clase de complejidad que contiene problemas de decisión que se pueden

resolver en un tiempo polinómico. Además, contiene a la mayoría de los problemas
naturales, algoritmos de programación lineal, funciones simples, etc., por ejemplo: la
suma de dos números naturales se resuelve en tiempo polinómico (para ser más
exactos, es de orden 2𝑛). Entre los problemas que se pueden resolver en tiempo
polinómico nos encontramos con diversas variedades como los logarítmicos
(log(𝑛)), los lineales (𝑛), los cuadráticos (𝑛 ), los cúbicos (𝑛 ) y así sucesivamente.
Volviendo al ejemplo principal, llegamos a la conclusión que la función de elevar al
cuadrado está contenida en la clase P.

La clase P

Los algoritmos de complejidad polinómica se dice que son tratables en el sentido

que suelen ser ejecutados en la práctica. En consecuencia, aquellos problemas para
los que la mejor solución que se conoce es de complejidad superior a la polinómica
se determinan como problemas intratables.

Optimización II
17
Tema 2. Ideas clave
Un ejemplo concreto de problemas de la clase P es justamente la multiplicación
matricial. A saber, si se consideran dos matrices 𝐴, 𝐵 ∈ ℳ × (ℝ), la idea es
determinar 𝐶 ∈ ℳ × (ℝ), tal que 𝐶 = 𝐴 ∙ 𝐵. La solución del problema está dada por:

Figura 7. Algoritmo para el producto de matrices de orden 𝑛. Fuente: elaboración propia.

Entonces, podemos establecer que:

 Un problema está en la clase P si existe un algoritmo determinista que puede

resolverlo en tiempo polinomial. En otras palabras, el tiempo requerido para
resolver el problema es una función polinomial del tamaño de la entrada.

 Los problemas P son eficientemente resolubles en el sentido de que se pueden

resolver en tiempo razonable, incluso para entradas grandes.

 Ejemplos de problemas P incluyen la suma de dos números, ordenar una lista de

elementos y encontrar el camino más corto en un grafo ponderado.

Optimización II
18
Tema 2. Ideas clave
La clase NP

La clase de complejidad NP contiene problemas que no pueden resolverse en un

tiempo polinómico. Cuando se dice que un algoritmo no puede obtener una solución
a un problema en tiempo polinómico siempre se intenta buscar otro procedimiento
que lo consiga mejorar. Frente a los problemas contenidos en P, tienen métodos de
resolución menos eficaces. Podemos ver que la operación de calcular la raíz cuadrada
se encuentra contenida en esta clase.

Si nos resulta sencillo encontrar una solución para un determinado problema,

sabremos comprobar si la solución es cierta (simplemente comparar), por lo
que P es un subconjunto de la clase NP.

NP es por tiempo polinomial no determinista (por sus siglas en inglés). Los algoritmos
de complejidad NP contienen problemas difíciles, pero verificar las soluciones es
fácil. No determinista significa que, a veces, tenemos que probar muchas posibles
soluciones antes de encontrar la correcta. Esto puede empujarnos a usar estrategias
diferentes, incluso el azar. Es como armar un rompecabezas gigante y probar unir
diferentes piezas hasta que encajen, sin un orden, simplemente al azar.

En los NP, podría ser muy difícil hallar la solución, quizá requeriría miles de millones
de años de computación, pero, una vez encontrada, es fácil de comprobar. Esta clase
de problemas se encuentran en un limbo informático en el que son considerados
como ejercicios sin solución (indecidibles) e irresolubles (intratables). Son la base de
la seguridad del cifrado en criptografía, opera en modelos precisos de previsión
financiera en el análisis del comportamiento del pliegue de proteínas en una célula
(como posible aplicación) y, más cotidiano aún, en el juego de SUDOKU o en la
búsqueda de horarios de vuelos.

Optimización II
19
Tema 2. Ideas clave
Existe una relación aún más compleja: los problemas NP-completos, que vienen
siendo una especie de subclase a los NP. Estos se consideran problemas llave porque,
si se encuentra una manera de resolver eficientemente solo uno de ellos, significa
que todos los NP pueden resolverse eficientemente, así que los ordenadores actuales
tomarían atajos para resolver dichos problemas en caso de comprobarse su igualdad.

Ejemplos como el del agente viajero persiguen explicar este conflicto con mejor
suficiencia. Supongamos que un comerciante necesita visitar clientes en varias
ciudades, conociendo la distancia entre cada una de ellas, y, por tanto, espera realizar
su recorrido empleando la ruta más corta y eficiente para evitar repetir alguna
ciudad. Surgen entonces preguntas naturales:

 ¿Cuántas posibles rutas puedes calcular y en cuánto tiempo?

 ¿Cuál es la más eficiente?

Las respuestas a estas preguntas se pueden verificar, pero requieren de un tiempo

suficientemente largo e imposible para resolverlas mediante un procedimiento
directo (fuerza bruta).

Un problema NP-completo

El matemático venezolano Rodolfo Nieves (2023) plantea el problema del milenio y

un algoritmo para idear un camino para su solución. A saber, la suma de subconjuntos
pertenece a la categoría NP-completo (de acuerdo con la literatura científica
existente) y su resolución —como problema llave— es equivalente a solucionar todos
los de esta categoría. Para el desarrollo de dicho algoritmo —y su respectiva
comprensión— iniciaremos con los siguientes enunciados, en forma de dos
planteamientos equivalentes.

 Planteamiento n°1: dado un conjunto de enteros, ¿existe algún subconjunto no

vacío cuya suma sea exactamente igual a Cero?

Optimización II
20
Tema 2. Ideas clave
 Planteamiento n°2: dado un conjunto de enteros y un entero S, ¿existe algún
subconjunto cuya suma sea igual a S?

La reducción de problemas implica demostrar que un problema es, al menos, tan

difícil de resolver como otro. Esto se utiliza en el estudio de problemas NP-completos,
donde se demuestra que un problema dado es, al menos, tan difícil como aquel más
difícil en NP. Ahora bien, si reducimos ese enunciado anterior, tenemos que:

Dado un conjunto de enteros 𝐶, cuya suma de sus elementos sea igual a S,

¿existe algún subconjunto 𝐵, perteneciente al conjunto 𝐶, cuya suma de los
elementos del subconjunto 𝐵 sea igual a S?

El próximo paso para llegar al algoritmo de solución es diseñar dos criterios y

certificados que establezcan las condiciones necesarias y suficientes para tratar
ambos planteamientos. El Criterio 1 permite abordar el Planteamiento 1 y el Criterio
2 tiene aplicación en el Planteamiento 2. La conjugación de ambos permite tratar el
problema de la suma de subconjuntos.

 Criterio 1: la condición necesaria y suficiente para que exista un subconjunto no

vacío 𝐵 (pero nulo), perteneciente a un conjunto 𝐴 cuya suma sea igual a
𝑆 (𝐴 = 𝑆). Solo es necesario y suficiente que exista un subconjunto: 𝐶 = 𝑆
perteneciente al conjunto 𝐴, tal que 𝐴– 𝑆 = 0 y, además, que 𝐴– 𝐶 = 0.

Para demostrar el funcionamiento del Criterio 1 tenemos que:

𝐴 = {−7 , −3 , −2 , 5 , 8} ⟼ 1
𝑆 = 1
𝐶 = {−7, 8} ⟼ 1
𝐵 = {−3 , −2 , 5} ⟼ 0
𝐴 – 𝑆 = {−7 , −3 , −2 , 5 , 8 , −1} ⟼ 0
𝑆 = 𝐶 = { −7 , −3 , −2 , 5 , 8 } = { −7 , 8 } ⟼ 1

Optimización II
21
Tema 2. Ideas clave
 Criterio 2: para que exista un subconjunto no vacío nulo 𝐶, perteneciente a un
conjunto 𝐴 cuya suma sea 𝑆, solo es necesario y suficiente que 𝐴 − 𝐶 = 𝐵, tal que
𝐵 sea un subconjunto no vacío ni nulo perteneciente al conjunto 𝐴. Un ejemplo,
para el Criterio 2 es:

𝐴 = {−7, −3 , −2 , 5 , 8 } = 1 𝐴 = { −7 , −3 , −2 , 5 , 8 } = 1
𝐴 = 𝑆 = 1 𝐴 = 𝑆 = 1
𝐶 = 4 𝐶 = 3
𝐴 – 𝐶 = 𝐵 = 1 – 4 = −3 𝐴 – 𝐶 = 𝐵 = 1 – 3 = −2
𝐵 = −3 𝐵 = −2
𝐶 = {5 , 8 , −7 , −2} = 4 𝐶 = {−2 , 5} = 3

Los criterios planteados, una vez analizados, sugieren un tratamiento efectivo al

problema de la suma de subconjuntos. Esto nos permite, a su vez, proponer un
pseudo código que logra transformar el problema de la suma de subconjuntos NP-
completo a un problema NP y, de igual forma, de NP-completo a P.

t=cputime (Tiempo de ejecución)

y=([10,-10,-5,16,-9]) (Conjunto de n elementos) (Entrada)
s=sum(y) (Función Suma de n elementos)
c=0 ó c=Cualquier entero (Constante o Parámetro de entrada)
x1=([y(1)])(Cualquiera de los 2n-1 Subconjuntos propios de la entrada)
sum(x1) (Función suma parcial del subconjunto propio)
s==sum(x1) (Salida lógica de existencia y comparación)
if ans==1 (Verificación y comprobación condicional (Criterio 1)
A=([y(1)]) (Subconjunto)
B=([y(2) y(3) y(4) y(5)]) (Subconjunto complementario)
disp(‘Existe un subconjunto: B=S’)(Criterio 1)
disp(‘Existe un subconjunto: A=0’)(Criterio 1)
break (Detención de la ejecución o rutina)(Bucle anidado)
else
disp(‘No existe un subconjunto: B=S’)(Criterio 1)
disp(‘No existe un subconjunto: A=0’)(Criterio 1)
end (Fin)
c==sum(x1) (Salida lógica de existencia y comparación)
if ans==1 (Verificación y comprobación condicional) (Criterio 2)

Optimización II
22
Tema 2. Ideas clave
A=([y(1)])(Subconjunto)
B=([y(2) y(3) y(4) y(5)]) (Subconjunto complementario)
disp(‘Existe un subconjunto complementario: A1=0’)(Criterio 2)
disp(‘Existe un subconjunto complementario: B=C’)(Criterio 2)
break (Detención de la ejecución o rutina)(Bucle anidado)
else
disp(‘No existe un subconjunto: A=0’)(Criterio 2)
disp(‘No existe un subconjunto: B=C’)(Criterio 2)
end (Fin)

P vs NP

Uno de los problemas no resueltos más famosos en la teoría de la computación es si

P es igual a NP. Esto se refiere a la pregunta de si los problemas cuyas soluciones se
pueden verificar rápidamente (NP) también se pueden encontrar rápidamente (P) o
si hay problemas que son más fáciles de verificar que de resolver.

En el siguiente enlace, podrás encontrar un vídeo acerca del problema de P vs NP

2.5. Cuaderno de ejercicios

Ejercicio 1

El programa de cálculo Matlab contiene los comandos tic y toc que nos permiten
comparar el costo de cálculo entre distintos algoritmos. Escribiendo la sentencia tic
al inicio del proceso y toc al final, obtendremos el tiempo empleado por la
computadora para completarlo.

Optimización II
23
Tema 2. Ideas clave
Queremos determinar una secuencia de sentencias para evaluar un polinomio de
grado 𝑁 = 10 en el valor 𝑡 = 1, tanto para la forma estándar como para la forma
de Horner.

Solución

Script de Horner:

%% Comparación Forma Estándar y Método de Horner

clear all
clc
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
N = 1e8; % Grado del Polinomio
a = 1:N; % Cantidad de coeficientes del polinomio
t = 1; % Punto de evaluación t_0=1
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Forma Estándar
tic
p = a(1);
for k = 2:N
p = p+a(k)*t^k;
end
toc
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Método de Horner
tic
pn = a(1);
for k = 2: N
pn = pn*t+a(k);
end
toc

La solución obtenida es:

Elapsed time is 3.234165 seconds.

Elapsed time is 0.509062 seconds.

Optimización II
24
Tema 2. Ideas clave
Ejercicio 2

¿Qué significa que el tiempo de ejecución de un algoritmo está en el orden exacto de

𝑓(𝑛)? Demostrar que 𝑇(𝑛) = 5 ∙ 2 + 𝑛 está en el orden exacto de 2 .

Solución

Para el primer planteamiento, debemos recordar la definición de notación asintótica.

En este sentido, podemos emplear la regla del límite para el cual consideramos:

 𝑓(𝑛) = 5 ∙ 2
 𝑔(𝑛) = 2

Luego, considerando 𝑛 como una variable real, podremos utilizar la regla de L’Hopital.
Veamos:

5∙2 +𝑛 5 ∙ 2 ∙ ln 2 + 2 ∙ 𝑛 5 ∙ 2 ∙ (ln 2) + 2
lim = lim = lim
→ 2 → 2 ∙ ln 2 → 2 ∙ (ln 2)

5 ∙ 2 ∙ (ln 2)
= lim = 5
→ 2 ∙ (ln 2)

Al final, hemos obtenido una constante numérica. En este caso, se concluye

directamente que: 𝑓(𝑛) ∈ 𝑂(𝑔(𝑛)).

Optimización II
25
Tema 2. Ideas clave
Ejercicio 3

Usando las definiciones de notación asintótica, demuestre si son verdaderas o falsas

las afirmaciones siguientes:

 Afirmación A: (𝑛 + 1)! ∈ 𝑂 3(𝑛!)

 Afirmación B: 𝑛 ∈ Ω((𝑛 + 1) )

Solución

(𝑛 + 1)! ∈ 𝑂 3(𝑛!) ⟼ Falso

Lo demostramos por reducción al absurdo. Si suponemos que es verdadero, entonces

existe 𝑐 > 0 y 𝑛 ∈ ℕ, tal que para todo 𝑛 ≥ 𝑛 se tiene que:

(𝑛 + 1)! ≤ 𝑐 ∙ 3 ∙ 𝑛!

Pero, entonces, tendríamos que para todo 𝑛 ≥ 𝑛 se tiene que 𝑛 + 1 ≤ 3𝑐, lo cual
es imposible.

(𝑏) 𝑛 ∈ Ω((𝑛 + 1) ) ⟼ Verdadero

Intentemos justificar las acotaciones pertinentes:

2 1
𝑛 ≥ 𝑐(𝑛 + 1) ⇒ 𝑛 ≥ 𝑐𝑛 + 𝑐2𝑛 + 𝑐 ⇒ 1 ≥ 𝑐 + 𝑐 + 𝑐
𝑛 𝑛

Así, basta tomar una constante 0 < 𝑐 ≤ para que se satisfagan las acotaciones para

todo 𝑛 > 1.

Optimización II
26
Tema 2. Ideas clave
Ejercicio 4

Demuestre las siguientes afirmaciones:

 ln 𝑛 ∈ 𝑜(𝑛 ) para cualquier 𝛼 > 0.

 𝑛 ∈ 𝑜(2 ) para cualquier 𝑘 > 0.

Solución

Para responder a estas condiciones, basta con tomar límites y aplicar la regla de
L’Hopital:

1
ln 𝑛 𝑛 ln 2 = lim 𝑛 1
lim = lim = lim = 0
→ 𝑛 → 𝛼𝑛 → 𝛼𝑛 𝑛 ln 2 → 𝛼𝑛 ln 2

Para el segundo caso, tenemos que:

𝑛 𝑘𝑛 𝑘 ∙ (𝑘 − 1) ∙ ∙ ∙ 2 ∙ 1
lim = lim = lim = 0
→ 2 → 2 ln 2 → 2 (ln 2)

Ejercicio 5

Resolver problemas NP-completos de manera exacta puede ser computacionalmente

costoso y, en muchos casos, impráctico para instancias grandes. Sin embargo, se
pueden implementar algoritmos aproximados o heurísticas para obtener soluciones
cercanas a la óptima en un tiempo razonable. Aquí hay un ejemplo de un código en
MATLAB para resolver el problema de la mochila (Knapsack Problem) mediante una
heurística voraz.

Optimización II
27
Tema 2. Ideas clave
Solución

%% El Problema de la Mochila
%% Datos Iniciales - Mochila con 10 objetos
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Valores de los objetos en euros:
V = [3 2 2 10 2 2 4 5 1 9];
%% Peso de los objetos en kg:
P = [2.3 8 5 1.5 2 3.1 3 4.5 6 7];
%% Capacidad máxima de la mochila
Cmax = 30;
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Índice de sensibilidad en términos del valor
D = [V;P]'; % Matriz de valores y Pesos
Orden = zeros(10,2); % Matriz de ceros para agregar productos - carro
%vacío
% Inicio del ciclo
for i = 1:1:10; % Ordenamiento debido al índice de sensibilidad
[s,j] = max(D(:,1)); % Ordenamiento debido al Valor
Orden(i,:) = D(j,:);
D(j,:) = [];
end
%% Ingresar productos a la mochila
x = zeros(10,1); % Vector de ceros (sin productos)
k = 0; % Contador que agrega productos en cada iteración
%% Inicio del ciclo
while Cmax > (Orden(:,2)'*x) % Comprueba restricción de Peso (Factible)
k = k+1; % Actualiza el contador
x(k,1) = 1; % Ingresa un producto
%% Determina valor y peso del producto
Valor = Orden(:,1)'*x;
Peso = Orden(:,2)'*x;
x';
if(k==10)
msgbox('se agregaron todos los productos')
end
end
x(k,1) = 0; % Eliminación del artículo excedente
disp('----- Solución en relación al valor ------')

Optimización II
28
Tema 2. Ideas clave
Valor = Orden(:,1)'*x % Valor acumulado con esta sensibilidad
Peso = Orden(:,2)'*x % Peso acumulado con esta sensibilidad
x' % Imprime la solución
disp('--------------------------------------------------------------')
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Índice de sensibilidad por peso
D = [V;P]';
Orden = zeros(10,2);
%% Inicio del ciclo
for i = 1:1:10; % Ordenamiento debido al índice de sensibilidad
[s,j] = min(D(:,2)); % Ordenamiento debido al peso
Orden(i,:) = D(j,:);
D(j,:) = [];
end
%% Ingresar productos a la mochila
x = zeros(10,1); % Vector de ceros (sin productos)
k = 0; % Contador que agrega productos en cada iteración

while Cmax > (Orden(:,2)'*x) % Comprueba restricción de Peso (Factible)

k = k+1; % Actualiza el contador
x(k,1) = 1; % Ingresa un producto
%% Determina valor y peso del producto
Valor = Orden(:,1)'*x;
Peso = Orden(:,2)'*x;
x';
if(k==10)
msgbox('se agregaron todos los productos')
end
end
x(k,1) = 0;
disp('----- Solución en relación al peso ------')
Valor = Orden(:,1)'*x % Valor acumulado con esta sensibilidad
Peso = Orden(:,2)'*x % Peso acumulado con esta sensibilidad
x' % Imprime la solución
disp('---------------------------------------------------------------')
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Índice de sensibilidad Valor/Peso
e = V./P; % División punto a punto
D = [V;P;e]'; % Matriz - Valor/Peso/Sensibilidad
Orden = zeros(10,3);

Optimización II
29
Tema 2. Ideas clave
%% Inicio del ciclo
for i = 1:1:10; % Ordenamiento debido al indice de sensibilidad
[s,j] = max(D(:,3)); % Ordenamiento debido al Valor/Peso
Orden(i,:) = D(j,:);
D(j,:) = [];
end
%% Ingresar productos a la mochila
x = zeros(10,1); % Vector de ceros (sin productos)
k = 0; % Contador que agrega productos en cada iteración

while Cmax> (Orden(:,2)'*x) % Comprueba restricción de Peso (Factible)

k = k+1; % Actualiza el contador
x(k,1) = 1; % Ingresa un producto
%% Determina valor y peso del producto
Valor = Orden(:,1)'*x; % Valor acumulado con esta sensibilidad
Peso = Orden(:,2)'*x; % Peso acumulado con esta sensibilidad
x'; % Imprime la solución

if(k==10)
msgbox('se agregaron todos los productos')
end
end
x(k,1)=0;
disp('----- Solución en cuanto al Valor/peso -----')
Valor=Orden(:,1)'*x % Valor acumulado con esta sensibilidad
Peso=(Orden(:,2)'*x) % Peso acumulado con esta sensibilidad
x' % Imprime la solución
disp('---------------------------------------------------------------')
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Índice de sensibilidad Peso/Valor
e=P./V; % División punto a punto
D = [V;P;e]'; % Matriz - Valor/Peso/Sensibilidad
Orden = zeros(10,3);
%% Inicio del ciclo
for i = 1:1:10; % Ordenamiento debido al indice de sensibilidad
[s,j] = min(D(:,3)); % Ordenamiento debido al Peso/Valor
Orden(i,:) = D(j,:);
D(j,:) = [];
end

Optimización II
30
Tema 2. Ideas clave
%% Ingresar productos a la mochila
x = zeros(10,1); % Vector de ceros (sin productos)
k = 0; % Contador que agrega productos en cada iteración

while Cmax> (Orden(:,2)'*x) % Comprueba restricción de Peso (Factible)

k = k+1; % Actualiza el contador
x(k,1) = 1; % Ingresa un producto
%% Determina valor y peso del producto
Valor=Orden(:,1)'*x;
Peso=(Orden(:,2)'*x);
x';
if(k==10)
msgbox('se agregaron todos los productos')
end
end
x(k,1)=0;
disp('----- Solución en cuanto al Peso/Valor -----')
Valor=Orden(:,1)'*x % Mejor valor con este indice de sensibilidad
Peso=(Orden(:,2)'*x) % Mejor peso con este indice de sensibilidad
x' % Imprime la solución

disp('------------------------ FIN ----------------------------------')

2.6. Referencias bibliográficas

Nieves, R. (2023, junio 14). La complejidad del problema del milenio P vs NP y

un algoritmo para su solución. Niböe. [Link]

Trefethen, L. N. y Bau III, D. (1997). Numerical Linear Algebra. Society for Industrial
and Applied Mathematics.
[Link]

Optimización II
31
Tema 2. Ideas clave