Existe um algoritmo para otimização da complexidade de tempo / espaço de algoritmos?

9

Nos anos 50, foram inventados vários métodos de minimização de circuitos para funções booleanas . Existe uma extensão desses métodos ou algo semelhante para otimizar a complexidade do tempo ou espaço dos algoritmos?

Por exemplo, uma implementação de classificação por bolhas como uma entrada para esse algoritmo produziria uma implementação de um algoritmo de classificação com complexidade de tempo mais próxima deO(nregistro⁡n).

algorithms turing-machines time-complexity optimization space-complexity Optimizer
fonte
1
Vá embora!! Nós, professores de CS, ganhamos a vida ensinando algoritmos sofisticados; sua sugestão nos deixaria sem emprego!
vonbrand 6/01/16
Bem ... o que você espera da IA ​​então?
Optimizer
A classificação de bolha não é uma função booleana. Pior, nem todos os algoritmos de classificação são equivalentes! Por exemplo, alguns não são estáveis.
Yuval Filmus
Você está certo, mas o tipo de bolha e o "tipo bom" são apenas um exemplo do que eu vejo como entrada e saída, não vamos nos concentrar nos detalhes.
Optimizer
@YuvalFilmus certamente retornando um array ordenado não é mais fácil do que retornar verdadeiro ou falso
vonbrand

Respostas:

11

Consulte o teorema da velocidade de Blum (sim, este artigo é menos informativo; consulte um livro sobre teoria da complexidade). Essencialmente, diz que existem programas para os quais existe um programa que executa o mesmo trabalho que é mais rápido por qualquer margem especificada para quase todos os dados de entrada.

Pelo teorema de Rice , é impossível saber se dois programas dados fazem o mesmo trabalho.

Sim, para algumas noções muito restritas de "programa", dado um exemplo, é possível construir o programa "melhor possível" para o trabalho. Classes importantes, até. Mas está muito longe de qualquer coisa capaz de expressar bolhas.

vonbrand
fonte