Introducción a la Complejidad Computacional

Prof. Diana Margot López Herrera1 , Prof. Javier Fernando Botı́a Valderrama2 ,
Prof. Juan Felipe Quintana3
1 Docente Principal de Lógica y Representación II
2 Asesor Temático para la materia Lógica y Representación II
3 Docente de Cátedra para la materia Lógica y Representación II

Facultad de Ingenierı́a. Departamento de Ingenierı́a de Sistemas

1 Contexto de la Complejidad Computacional

En el mundo de la algoritmia y la lógica, siempre se ha deseado cómo medir el tiempo de eje-
cución, determinar el tiempo de cómputo para almacenar datos, establecer si un algoritmo gen-
era un costo/beneficio para resolver un problema, o diseñar algoritmos que generen una solución
factible. Para abordar estos problemas, la complejidad computacional permite establecer
métodos teóricos para medir el costo en términos del tiempo o espacio que genera un algoritmo
durante su ejecución. El estudio de la complejidad computacional se le atribuye a un matemático
canadiense llamado Jack R. Edmonds en 1965, quien considero el estudio de los algoritmos desde
el punto de vista de los tiempos de ejecución polinómicos o también llamado NP-completitud.
Esta interpretación permitió establecer los fundamentos del buen algoritmo o algoritmo rápido, el
cual es el objetivo principal para diseñar algoritmos que generen soluciones factibles con uso de
pocos recursos computacionales.
Dentro de la complejidad computacional, el cálculo de la complejidad temporal es una de las
estrategias más utilizadas para demostrar teóricamente la eficiencia de un algoritmo. Por lo general,
la complejidad temporal determina el tiempo de ejecución de los cálculos que realiza un algoritmo
en términos de polinomios, asumiendo la cantidad de datos que son necesarios para describir el
problema de computación que debe resolver el algoritmo. Por ejemplo, si se desea calcular la matriz
inversa cuadrada de n filas x n columnas (n = n), el algoritmo por eliminación Gauss–Jordan es
una función polinomial n3 pero si se utiliza el algoritmo Strassen, la función polinomial se reduce
un poco a n2.807 . Estas funciones polinomiales es la representación clásica de la complejidad
computacional que se utilizará a lo largo de esta unidad, el cual se busca determinar cuando un
algoritmo proporciona soluciones solubles en un tiempo de cómputo corto y encontrar aquellos
algoritmos que generan soluciones con tiempos de ejecución largos que pueden ser catalogados
como intratables o insolubles. Para encontrar las funciones polinomiales, se explicará algunas
notaciones matemáticas para representar la complejidad computacional, su definición matemática
desde el punto de vista de la teorı́a de funciones y cálculo de predicados (tema visto en matemáticas
discretas I), y las clases de complejidad y sus propiedades principales.

1
2 Notación Asintótica
2.1 Concepto de Notación Asintótica y sus Tipos de Representación
La notación asintótica es una representación matemática de la complejidad computacional expre-
sado en términos polinómicos, el cual nos permite observar el crecimiento del costo computacional
a medida que una variable de referencia aumente su valor. Por ejemplo, si tenemos una función
polinómica f (n) = 5n − 3, es evidente que la función es lineal y por consiguiente, a medida que n
aumenta, la función tendrá un crecimiento lineal. Si comparamos dicha función con otra función,
g(n) = n2 − 1, obviamente g(n) tendrá un crecimiento cuadrático a medida que n es más grande.
Por supuesto, g(n) implica mayor costo computacional que f (n) si n ≥ 0.
A partir de la notación asintótica, se establece un conjunto de notaciones matemáticas para
expresar teóricamente la complejidad computacional. Sin lugar a dudas, la notación Big O es el
más popular para determinar el costo de un algoritmo. Esta notación determina una cota superior
en el comportamiento asintótico de una función polinómica de un algoritmo. Por ejemplo, si
consideramos f (n) = 5n − 3 y asumimos que 5n − 3 = O(n2 ), es evidente que f (n) tiene una escala
n menor o igual a n2 , puesto que el crecimiento asintótico de n2 es mucho más rápido que f (n)
cuando n es un valor o escala muy grande. Desde el punto de vista matemático, podemos afirmar
que:

f (n) = O(g(n)) (1)

donde f (n) y g(n) son dos funciones polinómicas.
La ecuación 1 significa que existen dos constantes, c y n0 , tal que cumple la siguiente propiedad:

• Si f (n) ≤ cg(n), significa que si nosotros usamos cualquier valor constante c, esta desigualdad
se cumplirá si n > n0 , donde n0 es una escala de la función f (n0 ) que es menor a la escala
n de la función g(n).

A modo de ejemplo, se puede interpretar la propiedad como se muestra a continuación:

Considerando f (n) = 5n − 3 y g(n) = nlog(n), si asumimos que 5n − 3 ≤ O(nlog(n)), se puede

afirmar que f (n0 ) = 5n0 − 3 tiene una escala menor o igual g(n) = nlog(n), lo cual n > n0 . Lo
anterior se puede ilustrar en la Fig. 1.

Figure 1: Ejemplo de la propiedad f (n) ≤ c(g(n))

Teniendo en cuenta el anterior ejemplo, la notación Big O permite especificar el peor caso de
comportamiento de un algoritmo cuando n aumenta o en caso que se compare dos o más funciones
polinómicas.
Cuando se desea ser más estricto con la desigualdad de la propiedad para la notación asintótica,
se utiliza otro tipo de representación llamada Notación Pequeña o. En esta notación, por
ejemplo, si f (n) = 5n − 3 se puede escribir como 5n − 3 = o(n2 ) pero 5n − 3 ̸= o(n). Lo anterior
permite establecer un ajuste de la propiedad de la notación asintótica como:

2
 f (n) < cg(n) (2)
La ecuación 2 indica que para un valor c > 0 hay alguna escala n0 donde todos los valores de
n > n0 . A diferencia de la notación Big O, para la notación o denota estrictamente menor que.
Ası́ como la notación Big O se enfoca en la cota superior, hay otra representación enfocada
en la cota inferior llamada Notación Big Ω u Omega. Usando la función √ f (n) = 5n − 3, la
notación Big Ω se puede representar
√ para este ejemplo como 5n − 3 = Ω( n), el cual indica que
5n − 3 es más grande o igual a n para valores grandes de n. Desde el punto de vista matemático,
la notación Big Ω se expresa como:

f (n) = Ω(g(n)) (3)

La ecuación 3 indica que al considerar una constante c y una variable n0 , se puede afirmar que
f (n) ≥ cg(n) siempre y cuando los valores de n sean mayores que n0 . Lo anterior esta indicando
una condición de más grande o igual que. Como la notación Big Ω busca una cota inferior, por
ejemplo, si tenemos la condición 5n − 3 = Ω(1), se esta asegurando que 5n − 3 es un lı́mite inferior
por una constante 1.
Si se desea una restricción más estricta como mayor que, se utiliza la Notación pequeña
omega o Notación ω. √En esta notación, si consideramos f (n) = 5n − 3, entonces se puede
asegurar que 5n−3 = ω( n) pero 5n−3 ̸= ω(n). Bajo esta interpretación, la propiedad cambiarı́a
a f (n) > cg(n), lo cual indicarı́a que hay una constante c > 0 para valores n0 > n.
Por último, si se desea encontrar una región de complejidad computacional limitada por las
cotas superior e inferior, se utiliza la Notación Big Θ o Notación Big Theta. Esta notación
es una combinación de las notaciones Big O y Big Ω, donde se establece un intervalo definido por
dos constantes, c1 , c2 y n0 :

c1 g(n) ≤ f (n) ≤ c2 g(n) (4)

2.2 Tabla Resumen de las Notaciones Asintóticas

A partir de las propiedades vistas en la subsección anterior, se muestra una tabla resumen de las
diferentes notaciones para el cálculo del costo computacional que se utilizarán a lo largo de la
unidad:

Notación Representación Definición

Big O f (n) = O(g(n)) ∃c, n0 |f (n) ≤ c(g(n))
Pequeña o f (n) = o(g(n)) ∀c > 0, ∃n0 |f (n) < c(g(n))
Big Ω f (n) = Ω(g(n)) ∃c, n0 |f (n) ≥ c(g(n))
Pequeña ω f (n) = ω(g(n)) ∀c > 0, ∃n0 |f (n) > c(g(n))
Big Θ f (n) = Θ(g(n)) ∃c1 , c2 , n0 |c1 g(n) ≤ f (n) ≤ c2 g(n)

Table 1: Tabla resumen de las notaciones asintóticas. El sı́mbolo | significa tal que, ∀ significa para
todo y ∃ significa existe un. En todas las notaciones se considera la condición ∀n > n0 .

2.3 Ejemplo 1 de la Notación Asintótica

Considerando dos funciones polinómicas, f (n) = 5247n2 y g(n) = 11n3 , se desea determinar cuál
de las dos funciones es más grande su costo computacional. Para encontrar dicha respuesta, una
estrategia es comparar ambas funciones a partir de valores grandes de n. Por ejemplo, si utilizamos
n = 100, se puede establecer que:

f (100) = 5247(100)2 = 52470000

g(100) = 11(100)3 = 11000000
En este primer análisis, para una escala n = 100, la función f (n = 100) es mayor a g(n = 100).
Sin embargo, si se aumenta el valor n = 500, ¿Se cumplirá la condición f (n) > g(n)?. Si se evalúa
para un valor más grande de n, se obtiene el siguiente resultado:

f (500) = 5247(500)2 = 1.3118x109

g(500) = 11(500)3 = 1.375x109

3
 En este caso, cambia la condición a f (n) < g(n) para valores grandes de n y por consiguiente,
se cumple el criterio n > n0 , siendo n0 = 100 y n = 500.
Una vez realizado este análisis preliminar, es importante conocer cuál es valor de n que permite
cumplir la condición f (n) < g(n). Una estrategia de análisis es crear una gráfica comparativa
entre ambas funciones y encontrar un punto de intersección entre ambas funciones. Lo anterior se
muestra en la Fig 2:

Figure 2: Comparación entre f (n) = 5247n2 y g(n) = 11n3

Como se puede observar en la Fig. 2, cuando n = 477, f (n) = g(n). Sin embargo, para valores
n > 477, se cumple la condición f (n) < g(n).
A partir del análisis realizado con ambas funciones polinómicas, se desea identificar cuál(es)
notación(es) se cumple(n) para este ejercicio. A continuación, se muestra el análisis en cada
notación:
• f (n) = O(g(n)): Es verdad que se cumple con la propiedad de esta notación puesto que
f (n) ≤ c(g(n)) satisface para valores n ≥ 477.
• f (n) = o(g(n)): Es verdad que se cumple con la propiedad de esta notación puesto que
f (n) < c(g(n)) satisface para valores n > 477.
• f (n) = Ω(g(n)): Es falso que se cumpla con la propiedad de esta notación puesto que la
condición f (n) ≥ c(g(n)) no satisface para valores n ≥ 477.
• f (n) = ω(g(n)): Es falso que se cumpla con la propiedad de esta notación puesto que la
condición f (n) > c(g(n)) no satisface para valores n > 477.
• f (n) = Θ(g(n)): Es falso que se cumpla con la propiedad de esta notación puesto que para
valores n ≥ 477, la propiedad c1 g(n) ≤ f (n) ≤ c2 g(n) no satisface la condición puesto que
se explicó previamente que f (n) = Ω(g(n)) no cumple para valores grandes de n.

2.4 Ejemplo 2 de la Notación Asintótica

Dado una función polinómica, f (n) = 3n2 + 7n + 4, determinar cuál de las siguientes notaciones
es más probable que se cumpla:
• 3n2 + 7n + 4 = Ω(n2 )
• 3n2 + 7n + 4 = ω(1)
Analizando 3n2 + 7n + 4 = Ω(n2 ) y asumiendo que g(n) = n2 , se puede determinar que a
medida que n es grande, se cumple con la propiedad f (n) ≥ c(g(n)). Por ejemplo, si n = 0
entonces f (0) = 4 y g(0) = 0 y por supuesto, a medida que n aumenta, f (n) > g(n).
Analizando 3n2 +7n+4 = ω(1), es evidente que para valores n ≥ 0, la propiedad f (n) > c(g(n))
se cumple si g(n) = 1.
Comparando ambos casos, es más probable que se utilice la notación 3n2 + 7n + 4 = Ω(n2 )
puesto que es válido para cualquier valor n ≥ 0.

4
3 Clases de Complejidad Computacional
3.1 Tiempo Polinómico, Logarı́tmico y Exponencial
En el análisis de algoritmos, es importante establecer cuando un algoritmo es eficiente para
resolver un problema en un determinado tiempo t. Para determinar la eficiencia algorı́tmica, es
necesario establecer un tiempo polinomial si la función f (n) es polinómica. Por lo general, un
buen diseño de un algoritmo se condiciona si su ejecución se cumple en un tiempo polinomial o
menor. Algunos ejemplos de tiempo polinomial son los siguientes:
• Si f (n) = 5n − 3, a medida que n es grande, la función tiene un comportamiento lineal lo
cual n es un tiempo polinomial.
• Si f (n) = n2.5 y g(n) = n3 , a medida que n es grande, f (n) tiene una escala menor a g(n)
puesto que siempre f (n) < g(n). Por consiguiente, n es un tiempo polinomial.
√
• Si f (n) = n y g(n) = n, a medida que n es grande, f (n) < g(n). Además, como el
crecimiento de una función raı́z cuadrada es menor a una función lineal, se puede asegurar
que n es un tiempo polinomial.
Aunque se pensaba inicialmente que los algoritmos de tiempo polinomial eran los más eficientes
y rápidos, la realidad es otra. En este caso, los algoritmos de tiempo constante y de tiempo
logarı́tmico se consideran más rápidos que los algoritmos de tiempo polinomial. Por ejemplo, si
se define O(nlog(n)) como un costo computacional log-lineal, se afirma que log-lineal es más crece
más rápido que un algoritmo lineal O(n) pero su crecimiento es más lento que un algoritmo O(n2 ).
Esta observaciones se puede identificar en la Fig. 3

Figure 3: Comparación entre una función log-lineal con respecto a O(n) y O(n2 )

Hasta este punto, se afirmar que los algoritmos de tiempo constante, logarı́tmico o polinomial
se consideran como algoritmos que resuelven problemas fáciles, lo cual son eficientes. Sin embargo,
no todos los problemas se pueden resolver en un tiempo logarı́tmico o polinomial puesto que hay
problemas catalogados como difı́ciles. Cuando decimos que un algoritmo es ineficiente, se refiere
a aquello problemas que se resuelven en un tiempo mayor a un tiempo polinómico. Este tipo de
algoritmos ineficientes suelen generar un tiempo super-polinomial donde los más comunes se
llaman tiempo exponencial, el cual comprende un rango entre O(exp(n)) y O(2n ). Otro tipo de
algoritmo ineficiente variante del tiempo exponencial es el famoso tiempo sub-exponencial, que
se cataloga como algoritmos menores a un tiempo exponencial pero más grandes que un tiempo
1
polinomial (por ejemplo, O(2(n 3 )) ).
A partir de los diferentes tiempos de solución algorı́tmica, se puede establecer una clasificación
de la complejidad algorı́tmica de acuerdo al tiempo de ejecución:

3.2 Clasificación de la Complejidad Algorı́tmica de acuerdo con Tiempo

de Ejecución
Teniendo en cuenta la anterior subsección, se muestra a continuación la clasificación de la comple-
jidad computacional desde la mayor a menor velocidad de ejecución del algoritmo:

5
 • Tiempo Constante O(1): Son algoritmos que no dependen del tamaño de n y son obvia-
mente, los algoritmos más rápidos que se puede diseñar.

• Tiempo Logarı́tmico O(log(n)): Esta clase de complejidad permite explicar como se puede
reducir la búsqueda binaria a la mitad si la búsqueda se realiza de forma logarı́tmica. Además,
el tiempo logarı́tmico permite entender como las iteraciones de un ciclo for de un algoritmo
se puede reducir a una fracción logarı́tmica de acuerdo al tamaño de entrada que utilice el
algoritmo.

• Tiempo Lineal O(n): Son algoritmos que generan un tiempo de ejecución polinomial.

• Tiempo Log-Lineal O(nlog(n)): Son algoritmos que tienen un tiempo de ejecución poli-
nomial pero con la posibilidad que sea super-polinomial. Algunos algoritmos con tiempo
Log-lineal son: programación dinámica y algoritmos divides y conquistarás.

• Tiempo Cuadrático O(n2 ): Son algoritmos con un tiempo de ejecución super-polinomial

y son comunes en aquellos algoritmos con ciclos for anidados o que realiza procesos de
ordenamiento.

• Tiempo Cúbico O(n3 ): Son algoritmos que tienen tres o más niveles de ciclos for. Otro
algoritmo clásico con tiempo cúbico es la multiplicación entre dos matrices de n filas por n
columnas, puesto que se debe computar n × n para obtener una nueva matriz resultante.

• Tiempo Exponencial O(2n ): Es uno de los peores escenarios para la ejecución de un

algoritmo puesto que el tiempo de ejecución puede tardar semanas, meses o años. En caso
que se tenga un problema cuyo algoritmo es de tiempo exponencial, se sugiere modificar
las condiciones del problema para reducirlo a un tiempo cúbico o cuadrático o generar una
aproximación matemática a la solución del problema.

• Tiempo Factorial O(n!): Es el peor escenario de la complejidad computacional cuyos

problemas se consideran irresolubles.

En las Fig. 4 y 5, se visualiza el crecimiento del costo computacional para varios tiempos de
complejidad computacional:

Figure 4: Complejidad computacional constante, logarı́tmica, lineal y log-lineal

3.3 Clasificación de la Complejidad Computacional de acuerdo con el

Tipo de Problema
Teniendo en cuenta los problemas fáciles y difı́ciles que resuelve o trata de resolver un algoritmo,
la complejidad computacional se puede relacionar con problemas P, NP y NP completitud. A
continuación, se explicará cada uno de ellos y su interpretación:

6
 Figure 5: Complejidad computacional cuadrática, cúbica y exponencial

3.3.1 Problemas P
Los problemas P usualmente se resuelven fácilmente en un tiempo polinómico, el cual se puede
clasificar entre un tiempo logarı́tmico hasta un tiempo cuadrático en el peor de los casos. Algunos
ejemplos de problemas P son los siguientes:
• El algoritmo Gale-Shapley es una popular solución para resolver problemas de propósito y
rechazo en el sector económico o de aceptación diferida en una negociación de mercados.
No obstante, una de las aplicaciones más populares del algoritmo Gale-Shapley es el em-
parejamiento de un matrimonio estable, el cual se considera una población de hombres y
mujeres, ambos con la misma cantidad de individuos n, tal que se han clasificado en un
grupo de acuerdo al orden de preferencia de cada individuo. En este caso, el algoritmo es-
tablece casar a los hombres con las mujeres de modo que no se presenten dos personas que
prefieran estar entre sı́ que con sus cónyuges. Por lo general, este tipo de problemas genera
un costo computacional O(n2 ) si la población es grande o O(n) si la población es pequeña.
• El algoritmo de la programación lineal es una de las más utilizadas para resolver problemas de
optimización lineal en ingenierı́a industrial o en economı́a, cuya tarea principal es maximizar o
minimizar una función objetivo (por ejemplo, maximizar las ganancias o minimizar costos de
producción) de acuerdo a unas restricciones lineales (por ejemplo, desigualdades x1 +x2 < 100
o x1 ≥ 50, entre otro tipo de restricciones). A partir del número de variables n que describa
el problema de optimización lineal, si n es grande, el costo computacional podrı́a llegar a ser
O(n3 ) y si n es pequeño, el costo computacional se reduce a O(n).
• El algoritmo del árbol de decisión es ampliamente utilizado para tareas de clasificación de
datos en machine learning, cuya finalidad es crear un modelo capaz de adaptarse a la dis-
tribución de los datos para clasificar con etiquetas si un conjunto de valores pertenece a la
clase 0 o la clase 1. Por lo general, la complejidad computacional de este algoritmo depen-
derá del tamaño de la base de datos, representado por n filas o registros por j columnas
o caracterı́sticas o variables. A partir de lo anterior, el árbol de decisión tiene un tiempo
lineal O(njd), siendo d la profundidad o tamaño del árbol, pero si ignoramos la profundi-
dad del árbol, el costo computacional del algoritmo puede variar entre un tiempo log-lineal
O(njlog(n)) y un tiempo cuadrático O(n2 j) (si la complejidad crece a una razón n2 , puede
llegar a ser un problema NP duro que se hablará en la otra subsección).

3.3.2 Problemas NP
Otro tipo de problema llamado NP o Tiempo polinomial no determinı́stico puede llegar a
ser verificado su solución algorı́tmica en un tiempo polinomial pero que puede cambiar el costo
computacional a peores escenarios si el tamaño de la entrada n es muy grande. Algunos algoritmos
que resuelven problemas NP son los siguientes:
• El algoritmo de la factorización es muy popular para facilitar la multiplicación de los factores
entre sı́ para verificar que es igual al número original (tal y como se trabaja habitualmente
en casos de factorización del álgebra clásica).

7
 • El algoritmo del isomorfismo de los grafos se especializa en verificar si dos redes son equiv-
alentes si se proporciona un mapa entre amabas que reduzca la redundancia del diseño de
redes de datos o si dos imágenes son equivalentes. Debido a los escenarios de aplicación de
c
este algoritmo, tiene un costo computacional cuasi-polinomial, es decir, O(2log(n) ), donde c
representa el tamaño de la red. Este tiempo cuasi-polinomial permite establecer que si el
tamaño de la red es pequeña, se puede explicar la solución del algorı́tmico de forma sencilla
en tiempo polinómico pero si el tamaño de la red aumenta, la complejidad del algoritmo
puede llegar a ser sub-exponencial en el peor de los casos.

3.3.3 Problemas Co-NP

Los problemas Co-NP se consideran como el complemento de un problema NP, es decir, si un
problema es NP su complemento Co-NP genera una respuesta, que de ser negativa o no, se puede
asegurar que el algoritmo puede resolver el problema en tiempo polinómico. En muchos casos, no
es necesario verificar que todas las respuestas que genera el algoritmo se puedan resolver en un
tiempo polinómico, solo basta con demostrar que una sola respuesta al problema se resuelve o no
en un tiempo polinómico. Algunos algoritmos que resuelven problemas Co-NP es el algoritmo de
factorización de enteros y el algoritmo de comprobación de números enteros.

3.3.4 Problemas NP Duro

Los problemas NP Duro al menos se usa la palabra duro para referirse a aquellos problemas más
duros de resolver que los tradicionales problemas NP. En este escenario, se busca demostrar que un
problema NP se reduce a un problema NP duro pero puede tarda mucho tiempo en comprobarlo.
Lo anterior quiere decir que si se muestra que un algoritmo genera una solución a un problema NP
duro, se tarda bastante tiempo en verificar si la solución es válida o no. Algunos problemas NP
duros son:

• Fórmulas Booleanas cualificadas (QBF): Este tipo de problema de la matemática discreta

que mezcla fórmulas de la lógica proposicional con fórmulas de la lógica de predicados con
cuantificadores. Los algoritmos que solucionan este tipo de problema se enfocan en resolver
problemas de inteligencia artificial o representación del conocimiento en ontologı́as (Ingenierı́a
de Requisitos).

• Cı́clo no Hamiltoniano: Es un problema de grafos popular para explicar si varias ciudades

conectadas por una red de carreteras es posible visitar todas las ciudades exactamente una
vez, sin recorrer ninguna carretera dos veces. En este caso, los vértices representan las
ciudades y las aristas son las carreteras y se desea saber si el grafo tiene un ciclo o camino
que utilice cada vértice exactamente una vez.

3.3.5 Problemas NP Completo

En la teorı́a de la complejidad computacional, hay una propiedad especial de los problemas NP
llamado completitud, el cual genera un tipo de problemas NP Completo. Por lo general, los
problemas NP Completo es la unión entre un problema NP y NP duro, cuya tarea principal es
encontrar una solución eficiente a cualquier problema NP-Completo. Si se resuelve un problema
NP-completo, se podrı́a asegurar que esta solución se aplicarı́a de forma eficiente a cualquier
problema NP. De esta manera, una solución eficiente a un problema NP-Completo produce una
solución eficiente a todos los problemas NP en un tiempo polinómico. Algunos problemas NP
Completo son:

• El problema del camino Hamiltoniano: Es un tipo de problema que busca determinar si

existe un camino que visite cada lugar una sola vez y regrese a su punto de partida.

• El problema del embalaje de contenedores: Es un tipo de problema que busca encontrar un

conjunto de elementos que pueda caber en determinadas cajas o contenedores. Este tipo de
problema es común en los servidores de almacenamiento de datos.

• EL problema del viajero comerciante: Es un tipo de problema enfocado en encontrar el

camino más corto posible que visite un viajero de acuerdo a una lista de ciudades exactamente
una sola vez y que retorne a su punto de partida.

8
3.3.6 Problemas PSPACE
Los problemas PSPACE es una colección de todos los problemas que pueden ser resueltos por un
computador al utilizar una cantidad de memoria RAM sin algún lı́mite de tiempo. Para muchos
cientı́ficos de la computación, los problemas PSPACE se considera como una generalización de
todos los problemas que deben ser resueltos por algoritmos en cualquier tiempo, ya sea desde un
tiempo polinómico hasta un tiempo sub-exponencial. Dentro de los ejemplos de los problemas
PSPACE, se encuentran aquellos videojuegos de nivel generalizado en Super Mario Bros o Monkey
Island, hasta juegos de estrategia donde se debe mover en una pantalla de nxn pixeles.
En la teorı́a de la complejidad computacional, se afirma que los problemas NP están contenidos
en problemas PSPACE, asumiendo que se dispone de un tiempo ilimitado para verificar todas las
respuestas que genera el algoritmo. Aunque se asume que PSPACE deberı́a ser una clase de
problema mayor que los problemas NP, lo cierto es que no hay ninguna prueba matemática que
lo demuestre. Por esta razón, se establece una conjetura matemática llamada NP ̸= PSPACE
y P ̸= PSPACE, el cual aún se desconoce si P ̸= NP o P = NP. Lo anterior es uno de los
problemas del milenio definido por la prestigiosa intitución The Clay Mathematics Institute.

3.3.7 Generalización de la Clasificación de los Problemas

A partir de las diferencias y retos de solución de los problemas para estimar el costo computacional
de los algoritmos que tratan de generar un solución factible, hay una relación aceptada por la
comunidad de la ciencias de la computación entre los diferentes problemas. A continuación, se
muestra una representación general de la clasificación de los problemas (Fig.6):

Figure 6: Representación general de la clasificación de los problemas de acuerdo a la complejidad

computacional

Nota: Se sugiere a modo de consulta, investigar el concepto de EXPTIME y EXPSPACE.

3.4 Análisis de Algunos Problemas P, NP, NP Completo y PSPACE

Considere una función f (n) = log 2 (n). Se desea conocer si f (n) es una función eficiente o inefi-
ciente. Para determinar cuál de las dos condiciones se cumple, se debe analizar que sucede si se
aumenta n:

n = 10 → f (n = 10) = log 2 (10) = 5.3012

n = 100 → f (n = 100) = log 2 (100) = 21.2076
n = 1000 → f (n = 1000) = log 2 (1000) = 47.7171

9
 n = 10000 → f (n = 10000) = log 2 (10000) = 84.8304
n = 100000 → f (n = 100000) = log 2 (100000) = 132.54
n = 100000000 → f (n = 100000000) = log 2 (100000000) = 339.3215
Por consiguiente, para valores grandes de n, f (n) = log 2 (n) crece más rápido que alguna
función polinomial debido a que la función logarı́tmica es una función exponencial pero el costo
computacional más bajo que una función lineal. En conclusión, un algoritmo con un costo f (n) =
log 2 (n) es eficiente y puede resolver problemas P. √
Ahora vamos a cambiar de función a h(n) = 2 n . Si analizamos para valores grandes de n, se
puede determinar el crecimiento del costo computacional:
√
1000
n = 1000 → h(n = 1000) = 2 = 3.3068x109
√
10000
n = 10000 → h(n = 10000) = 2 = 1.2677x1030
Obviamente, para valores grandes n, el costo computacional es alto pero su crecimiento√no
n
√ tiempo exponencial O(2 ) debido a que h(n) tiene un superı́ndice n.
alcanza a llegar a ser un
Por consiguiente, como n < n, se puede afirmar que h(n) es eficiente hasta casi un tiempo cúbico
y puede estar enfocado en resolver problemas NP o probablemente NP Duro.

4 Referencias
• Herbert S. Wilf. Algorithms and Complexity, University of Pennsylvania, Philadelphia, PA
19104-6395, 1994.

• Thomas Mailund. Introduction to Computational Thinking: Problem Solving, Algorithms,

Data Structures, and More, Apress, 2021.

• Thomas G. Wong. Introduction to Classical and Quantum Computing, Rooted Grove, Om-
aha, Nebraska, USA, 2022.

10