Complejidad temporal – Problema fácil y problema difícil

Criptomanía | Complejidad temporal. Problema “fácil” y problema “difícil”. Tiempo polinómico y tiempo exponencial. Sigue leyendo para saber más.

En informática y matemáticas se pueden clasificar los problemas en dos “grandes grupos”.

Los problemas pueden ser fáciles o difíciles.

¿De qué depende la facilidad o dificultad de un problema? De la eficiencia de un algoritmo para resolverlo.

Y ¿de qué depende la eficiencia de un algoritmo? Del número de operaciones básicas que tiene que realizar para resolver el problema.

Así pues la facilidad o dificultad de un problema depende la cantidad y complicación de las operaciones que hay que realizar para resolverlo. O lo que es lo mismo, la facilidad o dificultad de un problema depende de la cantidad de tiempo necesaria para resolverlo.

Los problemas, a día de hoy, se pueden clasificar en P (fáciles) y NP (difíciles). Además podemos diferenciar otra categoría dentro de los problemas NP, problemas NP-completos. Estos problemas se caracterizan porque cualquier problema NP puede clasificarse dentro de la categoría de uno de los problemas NP-completos que existen.

complejidad temporal

Se considera que si pudieras desarrollar un algoritmo eficiente para resolver un problema NP-completo (complejidad temporal exponencial) este algoritmo podría resolver CUALQUIER problema NP que caiga dentro de su categoría.

También está extendida la creencia de que no existe tal algoritmo capaz de resolver eficientemente un problema NP-completo.

Problema difícil – Ejemplo

Se considera un problema difícil la descomposición en números primos de números aleatorios grandes.

Este es el principio en el que se basan los primeros algoritmos criptográficos de dos claves (RSA y otros).

No existe ningún algoritmo que pueda calcular de manera eficiente la descomposición en números primos de un número.

La única forma de descomponer en números primos un número grande es INTENTARLO.

Por ejemplo, intenta factorizar 22 en números primos

— 2 no es factor de 11 porque el resultado de la división no es un número entero (3, 5 y 7 tampoco)

Luego, la factorización de 22 en números primos es

Parece fácil, pero ¿qué procedimiento hemos usado?

Hemos probado si 22 era divisible entre el primer número primo que conocemos, 2. Cómo si lo era, hemos intentado volver a dividir el resultado por los números primos que conocemos hasta el mismo (2, 3, 5, 7 y 11). Solo era divisible entre si mismo (es un número primo).

Y ¿qué pasa si el número es muy grande? Factoriza en números primos 12595348441

¿Difícil verdad? Solo cabe seguir el mismo proceso que hemos seguido para 22, solo que ahora es mucho más largo.

De hecho, si el número fuera lo suficientemente grande (miles de dígitos), ni si quiera conoces números primos ilimitados (matemático descubre el número primo más alto conocido hasta la fecha)

Además, si el número es lo suficientemente grande el tiempo necesario para resolverlo con los mejores procesadores disponibles es TAN alto (cientos de miles de años) que se considera totalmente irresoluble.

Si no te lo crees, encuentra la factorización en números primos de

¿Eres capaz de conseguirlo? Deja un comentario con la factorización y tu dirección bitcoin, te enviaré 50 dólares por la hazaña.

Complejidad temporal

La complejidad temporal es una forma de clasificar la dificultad de los problemas en función del tiempo (cantidad de operaciones) que tomaría resolverlos.

Así pues podemos distinguir a grandes rasgos dos categorías de “tiempos” (complejidad temporal) que diferencian los problemas “fáciles” y “difíciles”.

  • Tiempo polinómico: Problema fácil. Se considera que un problema se resuelve en “tiempo polinómico” si el número de operaciones que necesita calcular el algoritmo a medida que aumentamos la complejidad del problema crece con una expresión polinómica 
  • Tiempo exponencial: Problema difícil. Se considera que un problema requiere “tiempo exponencial” si el número de operaciones que debe hacer un algoritmo crece de manera exponencial 

Pero la cantidad de operaciones que tiene que hacer un algoritmo para resolver un problema no solo puede crecer polinómicamente o exponencialmente. Por eso se han estandarizados muchas otras “complejidades temporales”.

Aquí una tabla con ejemplos de complejidad temporal ordenados de fácil a difícil con ejemplos.

Complejidad temporal

NOMBREREPRESENTACIÓNEJEMPLO
Tiempo constanteCalcular si un número es par o impar
Tiempo logarítmicoEncuentra la posición de un número en una lista ordenada
Tiempo lineal Encontrar el número más grande de una lista desordenada
Tiempo cuadráticoOrdenar elementos en una lista
Tiempo polinómico

Incluye todo lo anterior. Por ejemplo, saber si un número es primo o no.
Tiempo exponencialEncontrar la forma más eficiente de multiplicar un grupo de matrices por fuerza bruta
Tiempo factorialResolver el problema del viajero por fuerza bruta
The following two tabs change content below.
Ingeniero mecánico, redactor e inversor FinTech. Apasionado del mundo de las criptodivisas y las aplicaciones de las diferentes blockchains.

Latest posts by Fernando Gomez (see all)

Be First to Comment

Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *