ZenoReduce

"O movimento é uma ilusão", dizia o sábio grego Ζήνων (que translitera para Zeno, Zenon ou Zenão). Ele tinha várias demonstrações dessa afirmação, e uma delas começava com uma tartaruga desafiando o ligeiro Aquiles: "duvido que você chegue aqui onde eu estou". Ora, Aquiles só precisa de uma rápida corrida para chegar onde a tartaruga está. Ou não?

Para ajudar, a tartaruga colocou no caminho um monte de bandeirinhas. A primeira bandeirinha está na metade do caminho entre Aquiles e a chegada. A segunda bandeirinha está na metade do caminho entre a primeira bandeirinha e a chegada, e assim por diante.

Olha só que curioso: quando o Aquiles estiver na primeira bandeirinha, ele ainda vai precisar passar pela segunda, que está no meio do caminho que falta. Quando ele chegar na segunda, ainda precisa passar pela terceira, e assim por diante. Não importa em qual bandeirinha ele esteja, sempre tem mais uma no meio do caminho restante. E se sempre falta uma bandeirinha, então ele nunca vai chegar na tartaruga! Daí a conclusão do Zeno, de que o movimento do Aquiles é só uma ilusão.

Para os gregos isso era um paradoxo, mas isso é porque eles desconheciam limites e séries convergentes. Hoje em dia nós sabemos que o tempo entre uma bandeirinha e outra sempre diminui, e eventualmente tende a zero. Nesse caso o paradoxo se dissolve, e a nossa intuição de que o Aquiles consegue chegar na tartaruga volta a ser verdadeira.

Agora imagine como seria divertido se tivéssemos na computação um conceito análogo! Por exemplo, para percorrer uma lista, um computador leva sempre o mesmo tempo em cada elemento. Mas em algum universo paralelo poderíamos ter um computador que, a cada elemento da lista, leva só metade do tempo do passo anterior. Ao invés de serem máquinas de Turing, nesse universo paralelo os computadores seriam máquinas de Zeno.

Na verdade, eu fiquei tão curioso em saber como seriam esses computadores que escrevi um emulador deles pra brincar:

Emulador de máquina de Zeno, escrito em python
Unit tests do emulador, usando pyunit e mox

A api do emulador fornece uma única operação: o ZenoReduce. Ele funciona como se fosse um reduce normal do python, mas o tempo que ele leva em cada iteração da lista é metade do tempo da iteração anterior. A complexidade do ZenoReduce é curiosa: ela é igual à complexidade da operação binária que você usa, e independente do tamanho da lista. A demonstração é simples e está na caixa azul:

Livros clássicos de complexidade, como o do Papadimitriou, calculam complexidade contando o número de passos que o algoritmo executa. Mas isso só vale para máquinas de Turing, onde os passos tem sempre a mesma duração. Na máquina de Zeno, temos que medir complexidade usando o tempo de execução, ao invés do número de passos.

Suponha que o ZenoReduce vai executar uma operação binária qualquer em cada elemento da lista, e essa operação tem uma complexidade O(f(x)). Logo, o primeiro passo do ZenoReduce leva O(f(x)), o segundo leva O(f(x))/2 e assim por diante. Assim, se a lista tem n elementos, então a complexidade total é:



Mas 2.O(f(x)) é o próprio O(f(x)), logo provamos que o valor de n realmente não importa.

Escrever programas usando o ZenoReduce é divertido, porque os melhores algoritmos para ele usualmente são os piores na máquina de Turing. Por exemplo, para verificar se um número é primo, podemos usar a versão abaixo:

import zeno

def is_prime(n):
  return zeno.zenoreduce(
    lambda x,y: x and (n%y!=0), 
    xrange(2,n), True)

Para rodar esse ZenoReduce, você precisa usar a função run da api, que liga o módulo de emulação. O run requer uma função sem parâmetros que será executada na máquina de Zeno:

>>> zeno.run(lambda:is_prime(10001))
(False, 0.15625, 0.0)

A saída é uma tupla: o primeiro elemento é o resultado (False, ou seja, 10001 não é primo), o segundo elemento é o tempo que ele levou pra rodar na sua máquina (wall time, 0.15s), e o terceiro é quanto tempo ele teria levado se tivesse rodado em uma máquina de Zeno (zero, ou melhor, um tempo tão pequeno que é menor que a precisão do python).

A complexidade desse algoritmo é O(mod), ou seja, quem domina é o tempo para calcular o resto de uma divisão. Nossos computadores modernos fazem divisão por hardware, então esse tempo é O(1), porém só até um certo limite. Quando o número é grande, você precisa usar uma lib de bignum, e a complexidade aumenta. Mas aí é só usar o ZenoReduce novamente!

def mod(x, n):
  return zeno.zenoreduce(
    lambda x,y: x-n if x>=n else x, 
    xrange(x), x)

Agora nós reduzimos o O(mod) para O(subtração), e podemos continuar até bater em alguma operação que seja O(1) para qualquer entrada!

(Leitores atentos podem achar que usar um ZenoReduce dentro de outro é trapaça, mas não é. Sempre que você consegue achar um limite superior para o tamanho de todas as listas envolvidas, você também consegue reescrever os ZenoReduces encadeados como um único ZenoReduce rodando sobre o produto cartesiano das listas. Provar isso fica como exercício para o leitor atento.)

Quão poderosas são as máquinas de Zeno? Certamente mais que as máquinas de Turing! Na verdade, para elas é facinho provar que P=NP. Vamos fazer isso mostrando uma solução em O(1) para o problema do Subset Sum: dado uma lista qualquer de inteiros, queremos saber se existe um subconjunto dela cuja soma seja zero (esse problema é NP-completo).

Uma estratégia seria gerar uma lista com todos os subconjuntos possíveis, e testar cada um deles em um ZenoReduce. Mas isso não é muito bom porque você precisaria armazenar os 2ⁿ subconjuntos, ocupando assim espaço exponencial.

Ao invés disso, nós podemos simplesmente contar de 0 até 2ⁿ-1, onde, para cada número, os bits dele indicam se o elemento correspondente deve ser somado ou não. Assim nós podemos iterar pelos subconjuntos sem precisar armazená-los.

Antes de começar, duas funções auxiliares. Em python, o built-in len() é O(1), mas se não fosse poderíamos usar isso aqui:

def list_length(x):
  return zeno.zenoreduce(
    lambda x,y: x+1, x, 0)

Podemos também fazer um função O(1) para potenciação:

def power(n, x):
  return zeno.zenoreduce(
    lambda x,y: x*n, xrange(x), 1)

Dados uma lista e um número, cujos bits representam os elementos da lista a serem somados, podemos fazer essa soma condicional em O(1):

def conditional_sum(elements, n):
  return zeno.zenoreduce(
    lambda x,y: 
      x + (y[1] if (n & power(2, y[0]) > 0) else 0), 
    enumerate(elements), 0)

Por fim, é só testar todos os subconjuntos possíveis, novamente em O(1):

def subset_sum(elements):
  return zeno.zenoreduce(
    lambda x,y: x or (conditional_sum(elements, y) == 0), 
    xrange(1, power(2, list_length(elements))), False)

Vamos testar:

>>> zeno.run(lambda:subset_sum([-7, -3, -2, 5, 8]))
(True, 0.015625, 0.0)
>>> zeno.run(lambda:subset_sum(range(1,15)))
(False, 16.75, 1.89e-09)

Veja como esse algoritmo é horrível na máquina de Turing e quase instantâneo na máquina de Zeno!

Outra coisa que não seria possível nesse universo paralelo é a criptografia RSA. De fato, dá pra fatorar um número em O(1) usando ZenoReduces!

def greatest_factor(value, n):
  return zeno.zenoreduce(
    lambda x,y: 
      max(x, y if value % power(n, y)==0 else x), 
    xrange(value), 0)

def factorize(n):
  return zeno.zenoreduce(
    lambda x,y: (x + [(y, greatest_factor(n, y))]) 
      if is_prime(y) and n%y==0 else x, 
    xrange(2, 1+n), [])

Testando:

>>> zeno.run(lambda:factorize(300))
([(2, 2), (3, 1), (5, 2)], 12.65625, 1.77e-15)

Nesse universo paralelo onde facilmente se prova que P=NP e fatoração é O(1), certamente a computação seria bem diferente! Mas o que você me diria se eu te falasse que podemos fazer algo parecido aqui no nosso universo mesmo?

Imagine que você tem algum cálculo qualquer que demoraria um milhão de anos pra rodar, mas que numa máquina de Zeno demoraria apenas um dia. Você pode fazer esse cálculo usando uma máquina de Turing também, e o truque não é nenhuma magia: é relatividade!

Basta deixar seu computador executando o cálculo, e pegar uma nave espacial que viaje a uma velocidade próxima da luz (qualquer coisa mais veloz que 0.999999999999999997c serve). Para você, vai passar apenas um dia, mas para o computador que ficou na Terra, vai passar um milhão de anos, graças ao efeito de dilatação do tempo. Fica como exercício para o leitor fazer uma nave tão rápida, e garantir que o computador ainda vai estar lá funcionando depois de um milhão de anos :)

Bônus: Ricbit Jam #2

Nós vimos como usar o ZenoReduce para testar primalidade, resolver o subset sum e fatorar um número em O(1). Você consegue fazer algo semelhante para ordenar uma lista? Se você topa o desafio, é só participar do Ricbit Jam #2:

Regras do Ricbit Jam #2

Dessa vez o Ricbit Jam vai dar um prêmio para o primeiro colocado: um Cubo de Rubik oficial do Google!

Participe para ganhar!