Límites de la computación: indecidible y lento

Un problema indecidible es una pregunta de sí o no para la que ningún programa puede dar siempre la respuesta correcta. Otros problemas sí tienen programa, pero tardan tanto en crecer los datos que no sirven en la práctica.

Saber dónde están esos dos límites te ahorra buscar algo imposible, y te avisa cuando una solución no escalará.

Un problema de decisión es una pregunta de sí o no sobre un dato. «¿Es 91 un número primo?» es uno. «¿Tiene esta lista un número repetido?» es otro.

Es decidible si existe un programa que, para cualquier dato, acaba y da la respuesta correcta. Casi todos los problemas que conoces lo son. Pero no todos.

El problema de la parada pregunta: dado un programa y su dato, ¿acabará o se quedará en bucle para siempre? Alan Turing demostró en 1936 que ningún programa lo resuelve siempre.

La idea es una paradoja. Supón que existe un detector. Escribimos un programa que lo consulta sobre sí mismo y hace lo contrario de lo que el detector prediga.

Un problema puede ser decidible y aun así inútil. Con la fuerza bruta pruebas todo y siempre aciertas. Pero a veces hay tantas posibilidades que no acabarías.

Ejemplo: tienes una lista de números y un objetivo. ¿Hay un subconjunto que sume el objetivo? Cada número está dentro o fuera: con n números hay 2 elevado a n subconjuntos.

# Fuerza bruta: probar todos los subconjuntos de una lista pequeña.
numeros = [4, 8, 15, 16]
objetivo = 23
n = len(numeros)
cuenta = 0
for mascara in range(2 ** n):
    suma = 0
    # Cada bit de la máscara dice si el número j entra en el subconjunto.
    for j in range(n):
        if (mascara // 2 ** j) % 2 == 1:
            suma = suma + numeros[j]
    if suma == objetivo:
        cuenta = cuenta + 1
        print("Sirve la máscara", mascara)
print("Subconjuntos revisados:", 2 ** n)
print("Los que suman", objetivo, ":", cuenta)
# Añade un quinto número a la lista y mira cuánto crece "revisados".

Si alguien te da un subconjunto, comprobar su suma es rápido: sumas unos pocos números. Encontrarlo desde cero puede exigir probar muchísimos.

Muchos problemas famosos son así: horarios sin choques, rutas de reparto, colocar paquetes. Hoy nadie sabe si existe un método rápido para todos ellos. Es una de las grandes preguntas abiertas de la informática.

Los Runs de abajo calculan en una línea las potencias y los factoriales que miden el crecimiento. Solo cuentan pasos: no miden tiempo, porque el tiempo depende de la máquina.

Un factorial crece aún más deprisa: ordenar diez paradas de un reparto de todas las formas posibles son 3.628.800 recorridos.

python3 -c "print(2 ** 10)"

python3 -c "print(2 ** 30)"

python3 -c "print(2 ** 40)"

python3 -c "import math; print(math.factorial(10))"

Elige una lista de 6 pesos de tu mochila y un objetivo, y busca con tu función todos los subconjuntos que lo suman.

Después cuenta cuántos subconjuntos revisó tu programa con 6, 12 y 18 números. ¿Qué pasa con ese número cada vez que añades seis números?