¿Existe un algoritmo generalizado para encontrar la función inversa de una función biyectiva arbitraria?
- Para que este algoritmo sea útil, debe detenerse una vez que se encuentre la respuesta correcta.
- Más allá del requisito de que finalmente debe encontrar la solución, no hay limitaciones de tiempo en el tiempo que lleva encontrar o ejecutar la función inversa (con eso en mente, algo mejor que la fuerza bruta de adivinar y verificar sería más interesante).
Por ejemplo, si existiera un algoritmo tan generalizado, podría resolver un algoritmo de descompresión para un algoritmo de compresión sin pérdidas.
EDITAR:
Realmente me gustaron las suposiciones de Evgenij Thorstensen, ya que resumieron mi pregunta bastante bien.
Supuestos
- Funciones biyectivas computables sobre un alfabeto fijo (digamos {0, 1})
- Representado por una máquina de Turing determinista (DTM) que lo calcula
- El algoritmo propuesto podría resolver un DTM que invertiría la salida de la función biyectiva original.
Otra oportunidad para explicarlo:
Dado: Función biyectiva Fque mapea X del dominio A en Y del dominio B.
El algoritmo propuesto debería ser capaz de resolver una función biyectiva Gque mapee Y desde el dominio B a X desde el dominio A, de modo que G(F(X))=Xy F * G = Idónde Iesté la función de identidad.
ds.algorithms
Kendall Hopkins
fuente
fuente
Respuestas:
Ha habido documentos sobre la conversión automática de algoritmos para funciones biyectivas en algoritmos para la función inversa; mi primer documento de conferencia fue uno de esos. Pero la clase de algoritmos que pueden invertirse de esta manera está severamente limitada, como ya sugieren las otras respuestas.
fuente
En un dominio completamente desestructurado, lo mejor que puede hacer es la búsqueda de fuerza bruta, que lleva un tiempo lineal en el tamaño del dominio. Sin embargo, si el dominio del que habla es cadenas de n bits, eso es exponencial en n.
(Tenga en cuenta que, si hubiera un inversor eficiente de función totalmente general, invertir la función de multiplicación de enteros le daría un algoritmo de factorización eficiente).
fuente
Como @arnab señaló en los comentarios, las permutaciones unidireccionales son una primitiva criptográfica. Si desea invertir funciones arbitrarias de manera eficiente, tendrá que superar las barreras criptográficas (además de la factorización).
fuente
Como muchos en esta página ya han señalado, la solución en general podría ser intratable.
No todo está perdido si está interesado en la programación invertible. Una alternativa para encontrar el inverso de una función dada es construir su función a partir de la composición de funciones invertibles, en cuyo caso encontrar el inverso es trivial.
Un ejemplo de este enfoque (usando Haskell) se explica en este documento http://www.cs.ru.nl/A.vanWeelden/bi-arrows/
Como sucede, he usado Biarrow para ayudarme a escribir solo una dirección de un algoritmo de compresión y obtener la otra (descompresión) de forma gratuita (libre podría ser la palabra incorrecta, son difíciles de usar, debido a la falta de soporte de idioma) .
fuente
Aquí hay un algoritmo manual bajo algunas suposiciones fuertes.
Supuestos
Con estos supuestos, podemos mirar el DTM de entrada e invertir todas las transiciones (los estados de detención se convierten en estados de inicio, la lectura se convierte en escritura y viceversa, leemos desde el final, la izquierda es la derecha, etc.). Como la TM es determinista y la función calculada es biyectiva, el resultado también es una TM y calcula el inverso.
Tenga en cuenta que esto no funcionará para factorizar, porque la multiplicación no es biyectiva. La multiplicación de los números primos es , si ignoramos el orden, pero una TM que multiplica números no calcula "solo" la función biyectiva que queremos, calcula "demasiado", de ahí mi segunda suposición (sí, es bastante fuerte). Esto se relaciona muy bien con los comentarios sobre la representación.
fuente