Existe um algoritmo generalizado para encontrar a função inversa de uma função bijetiva arbitrária?
- Para que esse algoritmo seja útil, ele deve ser interrompido assim que a resposta correta for encontrada.
- Além do requisito de que ela deva encontrar a solução eventualmente, não há restrições de tempo para encontrar ou executar a função inversa (com isso em mente, algo melhor do que a força bruta de adivinhação e verificação seria mais interessante).
Por exemplo, se esse algoritmo generalizado existisse, ele poderia resolver um algoritmo de descompressão para um algoritmo de compressão sem perdas.
EDITAR:
Gostei muito das suposições de Evgenij Thorstensen, pois resumiram minha pergunta bastante bem.
Premissas
- Funções bijetivas computáveis sobre um alfabeto fixo (digamos {0, 1})
- Representado por uma máquina de Turing determinística (DTM) que a calcula
- O algoritmo proposto seria capaz de resolver um DTM que inverteria a saída da função bijetiva original.
Outra chance de explicar isso:
Dado: Função bijetiva Fque mapeia X do domínio A para Y do domínio B.
O algoritmo proposto deve ser capaz de resolver uma função Bijective Gque mapeia Y do domínio B para X do domínio A, de modo que G(F(X))=Xe F * G = Ionde Iestá a função de identidade.
ds.algorithms
Kendall Hopkins
fonte
fonte
Respostas:
Houve trabalhos sobre a conversão automática de algoritmos para funções bijetivas em algoritmos para a função inversa; meu próprio trabalho na primeira conferência foi um deles. Mas a classe de algoritmos que podem ser invertidos dessa maneira é severamente limitada, como as outras respostas já sugerem.
fonte
Em um domínio completamente não estruturado, o melhor que você pode fazer é a pesquisa de força bruta, que leva tempo linear no tamanho do domínio. No entanto, se o domínio do qual você está falando é de n bits, isso é exponencial em n.
(Observe que, se houvesse um inversor eficiente de função totalmente geral, a inversão da função de multiplicação inteira forneceria um algoritmo de fatoração eficiente.)
fonte
Como o @arnab apontou nos comentários, as permutações unidirecionais são um primitivo criptográfico. Se você deseja inverter funções arbitrárias com eficiência, terá barreiras criptográficas a serem superadas (além de fatorar).
fonte
Como muitos nesta página já apontaram, a solução em geral pode ser intratável.
Nem tudo está perdido se você estiver interessado em programação invertível. Uma alternativa para encontrar o inverso para uma determinada função é construir sua função a partir da composição de funções invertíveis; nesse caso, encontrar o inverso é trivial.
Um exemplo dessa abordagem (usando Haskell) é explicado neste documento http://www.cs.ru.nl/A.vanWeelden/bi-arrows/
Por acaso, usei o Biarrow's para me ajudar a escrever apenas uma direção de um algoritmo de compactação e obter a outra (descompactação) de graça (livre pode ser a palavra errada, é difícil de usar, devido à falta de suporte ao idioma) .
fonte
Aqui está um algoritmo ondulado sob algumas suposições fortes.
Premissas
Com essas suposições, podemos olhar para o DTM de entrada e inverter todas as transições (estados de parada se tornam estados de início, leitura se torna escrita e vica versa, lemos do final, esquerda é direita, etc.). Como a MT é determinística e a função calculada é bijetiva, o resultado também é uma MT e calcula o inverso.
Observe que isso não funcionará para fatoração, porque a multiplicação não é bijetiva. A multiplicação de números primos é , se desconsiderarmos a ordem, mas uma MT que multiplica números não computa "apenas" a função bijetiva que queremos, calcula "demais", daí a minha segunda suposição (sim, é bastante forte). Isso está muito bem relacionado aos comentários sobre representação.
fonte