¿Hay alguna clase de funciones que requieran recursos demostrablemente diferentes para calcular en lugar de calcular su inversa?

15

Disculpas de antemano si esta pregunta es demasiado simple.

Básicamente, lo que quiero saber es si hay alguna función F(X) con las siguientes propiedades:

Tome Fnorte(X) como F(X) cuando el dominio y el codominio están restringidos a cadenas de norte bits. Luego

  1. Fnorte(X) es inyectiva
  2. Fnorte(X) es surjective
  3. Fnorte(X) requiere estrictamente menos recursos (espacio / tiempo / profundidad del circuito / número de compuertas) para calcular bajo un modelo razonable queFnorte-1(y) , dondey=Fnorte(X) .
  4. La diferencia de recursos para Fnorte(X) vs f1(y) escala como una función estrictamente creciente de n .

Puedo encontrar ejemplos en los que la función sea sobreyectiva o inyectiva, pero no ambas, a menos que recurra a un modelo computacional artificial. Si elijo un modelo computacional que permite desplazamientos a la izquierda en unidad de tiempo en algún anillo, pero no desplazamientos a la derecha, entonces, por supuesto, es posible obtener una sobrecarga lineal (o superior si considera que una permutación más complicada es primitiva) . Por esta razón, solo me interesan los modelos razonables, por lo que me refiero principalmente a máquinas de Turing o circuitos NAND o similares.

Obviamente, esto debe ser cierto si PNP , pero parece que esto también es posible si P=NP , por lo que no debería equivaler a decidir esa pregunta.

Es completamente posible que esta pregunta tenga una respuesta obvia o un obstáculo obvio para responder, lo que me he perdido.

Joe Fitzsimons
fuente
3
Esta no es un área que entiendo bien, pero parece que está buscando una permutación en n bits que es difícil de invertir. Recuerdo haber leído en un artículo de Hastad ( nada.kth.se/~johanh/onewaync0.ps ) que existen permutaciones que están en , pero son P-difíciles de invertir. NC0
Robin Kothari
1
Véanse también referencias a trabajos anteriores en el artículo de Håstad de 1987. Menciona que Boppana y Lagarias (1986) dan un ejemplo de una permutación que está en NC 0 , pero no puede invertirse en NC 0 . 00
Jukka Suomela
1
Gracias, esto es exactamente lo que estaba buscando. Tal vez uno de ustedes quiere volver a publicar como respuesta? ¿Sabes si hay algo similar para la complejidad del tiempo?
Joe Fitzsimons

Respuestas:

10

Me pidieron que volviera a publicar mi comentario. Señalé este artículo de Hastad, que muestra que existen permutaciones en que son P-difíciles de invertir:norteC0 0

http://dx.doi.org/10.1016/0020-0190(87)90053-6 (PS)

Robin Kothari
fuente
Gracias, eso y el seguimiento de Jukka fueron exactamente el tipo de cosas que estaba buscando.
Joe Fitzsimons
5

Para circuitos booleanos sobre una base binaria completa (siendo la medida de complejidad el número de puertas en un circuito mínimo), la relación más conocida para permutaciones C ( f - 1 )C(F). Hasta donde yo sé, la mejor constante fue obtenida eneste trabajopor Hiltgen y es igual a 2.C(F-1)C(F)=Conortest

Editar. Como desea que la proporción aumente cuando crece, esto no responde a su pregunta. Sin embargo, para los circuitos booleanos sobre una base binaria completa, no se conoce nada mejor.norte

Grigory Yaroslavtsev
fuente
Bueno, el hecho de que no se sepa nada mejor es de hecho una respuesta.
Joe Fitzsimons
También sugiero leer la sección 1.2 "Asimetría computacional" del siguiente artículo: Jean-Camille Birget, Permutaciones unidireccionales, asimetría computacional y distorsión, Journal of Algebra, 320 (11), Computational Algebra, 1 de diciembre de 2008, páginas 4030-4062 . Además, puede estar interesado en este enlace: springerlink.com/content/4318u2t21682752u
MS Dousti
Una continuación del trabajo de Hiltgen es un artículo de Hirsh y Nikolenko que muestra una función con un espacio constante entre calcularlo e invertirlo, pero donde también hay una trampilla que permite una inversión más fácil: logic.pdmi.ras.ru/~hirsch/ papers / 09csr.ps.gz
usuario686
Vea también esta charla de Massey: iacr.org/publications/dl/massey96/html/massey.html
user686
Finalmente, permítanme agregar que sería un gran avance mostrar la existencia de una familia de funciones con un espacio súper constante: mostrar dicho espacio implicaría que (la versión de búsqueda de) circuit-SAT no tiene circuitos de tamaño lineal .
usuario686
0

En primer lugar, quería señalar que la surjectividad no está bien definida sin definir primero el codominio de la función. Entonces, en mi descripción a continuación, me referiré explícitamente al codominio sobre el cual la función es sobreyectiva.

Tanto el logaritmo discreto como las funciones RSA son permutaciones que se conjetura que son difíciles de invertir. A continuación, describiré la función de logaritmo discreto.

pagnortenortesolZpagnorteFnorte:ZpagnorteZpagnorteFnorte(X)=solX(modificaciónpagnorte)

FnorteZpagnorteFnorte

MS Dousti
fuente
Bueno, tienen la misma complejidad para calcular e invertir en una computadora cuántica, por lo que supuse que no había una prueba de que necesitaran recursos diferentes, solo un montón de intentos fallidos para crear algoritmos de tiempo polinomiales.
Joe Fitzsimons
2
Ok, creo que quizás no entiendes el punto de mi pregunta. Sé que hay una gran cantidad de funciones que se cree que son difíciles de invertir, y esto forma la base de la criptografía de clave pública. Lo que busco es un caso en el que hay una diferencia comprobada, incluso si es relativamente leve (estaría perfectamente satisfecho con una función que toma O (n) para calcular y O (n log n) para invertir, por ejemplo).
Joe Fitzsimons
[Con respecto al primer comentario] Está buscando una familia de permutaciones unidireccional. La mera existencia de tales construcciones, incluso en el modelo de cómputo de la Máquina Turing, aún no se ha probado (lo que demuestra una prueba de la existencia de criptografía de clave pública. Ver el caso 5 en cstheory.stackexchange.com/questions/ 1026 / ... ) Por lo tanto, no puede confiar en suposiciones no comprobadas. Sin embargo, si desea una suposición que funcione tanto en el modelo de Turing Machine como en el modelo Quantum, puedo proporcionarle detalles de los supuestos basados ​​en la dureza del "problema de celosía".
MS Dousti
1
Solo busco una forma muy débil de función unidireccional, y no estoy seguro del estado del problema para condiciones suficientemente débiles. Ciertamente no necesito una diferencia exponencial.
Joe Fitzsimons
2
No, la complejidad temporal se rige por la complejidad temporal del exponencial modular en todos los casos que mencione. El exponencial modular es la parte lenta del algoritmo de Shor, por lo que no hay más que una diferencia constante en la escala asintótica.
Joe Fitzsimons