La complejidad del caso genérico es un subcampo de la teoría de la complejidad computacional que estudia la complejidad de los problemas computacionales en "la mayoría de las entradas".
La complejidad del caso genérico es una forma de medir la complejidad de un problema computacional al descuidar un pequeño conjunto de entradas no representativas y considerar la complejidad del peor de los casos en el resto. Lo pequeño se define en términos de densidad asintótica. La aparente eficacia de la complejidad de los casos genéricos se debe a que, para una amplia variedad de problemas computacionales concretos, los casos más difíciles parecen ser raros. Los casos típicos son relativamente fáciles.
Este enfoque de la complejidad se originó en la teoría combinatoria de grupos , que tiene una tradición computacional que se remonta a principios del siglo pasado. La noción de complejidad genérica se introdujo en un artículo de 2003, [1] donde los autores demostraron que para una gran clase de grupos generados finitamente, la complejidad temporal genérica de algunos problemas de decisión clásicos de la teoría combinatoria de grupos, es decir, el problema verbal , el problema de conjugación y la pertenencia. problema , son lineales.
En las encuestas se puede encontrar una introducción detallada de la complejidad de los casos genéricos. [2] [3]
Definiciones basicas
Densidad asintótica
Sea yo un conjunto infinito de entradas para un problema computacional.
Definición 1. Una función de tamaño en I es un mapacon rango infinito. La bola de radio n es.
Si las entradas están codificadas como cadenas sobre un alfabeto finito, el tamaño podría ser la longitud de la cadena.
Dejar ser un conjunto de distribuciones de probabilidad dondees una distribución de probabilidad en. Si las bolas son finitos, entonces cada puede tomarse como la distribución equiprobable que es el caso más común. Nótese que solo un número finitopueden estar vacías o tener ; los ignoramos.
Definición 2. La densidad asintótica de un subconjunto es cuando existe este límite.
Cuando las bolas son finitos y es la medida equiprobable,
En este caso suele ser conveniente utilizar esferas en lugar de pelotas y definir . Un argumento que utiliza el teorema de Stolz muestra que existe si hace, y en ese caso son iguales.
Definición 3 es genérico si y insignificante si . X es exponencialmente (superpolinomialmente) genérico si la convergencia al límite en la Definición 2 es exponencialmente (superpolinomialmente) rápida, etc.
Un subconjunto genérico X es asintóticamente grande. Que X parezca grande en la práctica depende de qué tan rápido converge a 1. La convergencia superpolinomial parece ser lo suficientemente rápida.
Clases de complejidad genérica
Definición 4 Un algoritmo está en GenP (genéricamente tiempo polinomial) si nunca da respuestas incorrectas y si da respuestas correctas en tiempo polinomial en un conjunto genérico de entradas. Hay un problema en GenP si admite un algoritmo en GenP . Lo mismo ocurre con GenL ( tiempo genéricamente lineal ), GenE ( tiempo genéricamente exponencial con un exponente lineal) GenExp (tiempo genéricamente exponencial), etc. ExpGenP es la subclase de GenP para la que el conjunto genérico relevante es exponencialmente genérico.
De manera más general para cualquier podemos definir la clase Gen (f) correspondiente a la complejidad de tiempo O ( f ) en un conjunto genérico de entrada.
Definición 5. Un algoritmo resuelve un problema de forma genérica si nunca da respuestas incorrectas y si da respuestas correctas en un conjunto genérico de entradas. Un problema se puede resolver genéricamente si se resuelve genéricamente mediante algún algoritmo.
Teoría y aplicaciones
Problemas de teoría combinatoria de grupos
- Los famosos problemas indecidibles : bajo hipótesis adecuadas, los problemas de palabra, conjugación y decisión de pertenencia son genéricamente polinomiales. [1]
- Los problemas de búsqueda de palabras y conjugaciones están en GenP para todos los grupos fijos presentados de forma finita. [4]
- El conocido procedimiento de enumeración de clases laterales admite un límite superior computable en un conjunto genérico de entradas. [5]
- El algoritmo de Whitehead para probar si un elemento de un grupo libre está mapeado o no a otro por un automorfismo tiene un límite superior exponencial en el peor de los casos, pero funciona bien en la práctica. Se muestra que el algoritmo está en GenL . [6]
- El problema de la conjugación en las extensiones HNN puede ser irresoluble incluso para grupos libres . Sin embargo, es genéricamente tiempo cúbico. [7]
El problema de la detención y el problema de la correspondencia postal
- El problema de la detención de la máquina de Turing con cinta de una cara es fácilmente decidible la mayor parte del tiempo; está en GenP [8]
Se desconoce la situación de la cinta de dos caras. Sin embargo, existe una especie de límite inferior para las máquinas de ambos tipos. El problema de la detención no está en ExpGenP para ningún modelo de máquina de Turing, [9] [10]
- El problema de la correspondencia postal está en ExpGenP . [2]
Aritmética de Presburger
El problema de decisión para la aritmética de Presburger admite un doble límite inferior exponencial en el peor de los casos [11] y un triple límite superior exponencial en el peor de los casos. Se desconoce la complejidad genérica, pero se sabe que el problema no está en ExpGenP . [12]
NP completa problemas
Como es bien sabido que los problemas NP-completos pueden ser fáciles en promedio, no es de extrañar que varios de ellos también sean genéricamente fáciles.
- El problema de tres satisfacibilidad está en ExpGenP . [13]
- El problema de la suma de subconjuntos está en GenP . [2]
Funciones unidireccionales
Existe una versión de complejidad genérica de una función unidireccional [14] que produce la misma clase de funciones pero permite considerar diferentes supuestos de seguridad de los habituales.
Criptografía de clave pública
Una serie de artículos [15] [16] [17] está dedicada al criptoanálisis del protocolo de intercambio de claves Anshel-Anshel-Goldfeld , cuya seguridad se basa en suposiciones sobre el grupo trenzado . Esta serie culmina en Miasnikov y Ushakov (2008) [18] que aplica técnicas de complejidad de casos genéricos para obtener un análisis completo del ataque basado en la longitud y las condiciones en las que funciona. El punto de vista genérico también sugiere una especie de nuevo ataque llamado ataque del cociente y una versión más segura del protocolo Anshel-Anshel-Goldfeld.
Lista de resultados teóricos generales
- Un famoso teorema de Rice establece que si F es un subconjunto del conjunto de funciones computables parciales de a , entonces, a menos que F o su complemento estén vacíos, el problema de decidir si una máquina de Turing en particular calcula una función en F es indecidible. El siguiente teorema da una versión genérica.
Teorema 1 [19] Sea yo el conjunto de todas las máquinas de Turing. Si F es un subconjunto del conjunto de todas las funciones computables parciales dea sí mismo tal que F y su complemento son a la vez que no está vacía, entonces el problema de decidir si es o no una máquina de Turing dada calcula una función de F no es decidible en cualquier subconjunto de manera exponencial genérica de I .
- Los siguientes teoremas son de: [1]
Teorema 2 El conjunto de lenguajes formales que son genéricamente computables tiene medida cero.
Teorema 3 Existe una jerarquía infinita de clases de complejidad genérica. Más precisamente para una función de complejidad adecuada f ,.
- El siguiente teorema muestra que así como hay problemas de casos completos promedio dentro de los problemas de distribución NP,
También existen problemas genéricos de casos completos. Los argumentos en el caso genérico son similares a los del caso promedio, y el problema de caso completo genérico también es caso completo promedio. Es el problema de la detención delimitado por la distribución .
Teorema 4 [2] Existe una noción de reducción de tiempo polinomial genérico con respecto a la cual el problema de detención acotado distribucional es completo dentro de la clase de problemas NP distributivos.
Comparaciones con trabajos anteriores
Tiempo casi polinomial
Meyer y Paterson [20] definen un algoritmo como tiempo casi polinómico, o APT, si se detiene dentro de p (n) pasos en todas las entradas excepto p (n) de tamaño n . Claramente, los algoritmos APT están incluidos en nuestra clase GenP . Hemos visto varios problemas completos de NP en GenP , pero Meyer y Paterson muestran que este no es el caso de APT. Demuestran que un problema NP completo se puede reducir a un problema en APT si y solo si P = NP . Por lo tanto, APT parece mucho más restrictivo que GenP .
Complejidad de casos promedio
La complejidad de los casos genéricos es similar a la complejidad de los casos promedio . Sin embargo, existen algunas diferencias significativas. La complejidad de caso genérico es una medida directa del rendimiento de un algoritmo en la mayoría de las entradas, mientras que la complejidad de caso promedio proporciona una medida del equilibrio entre instancias fáciles y difíciles. Además, la complejidad del caso genérico se aplica naturalmente a problemas indecidibles .
Suponer es un algoritmo cuya complejidad temporal , es polinomio en promedio. ¿Qué podemos inferir sobre el comportamiento de en entradas típicas?
Ejemplo 1 Sea I el conjunto de todas las palabras sobre y define el tamaño tener la longitud de una palabra, . Definirpara ser el conjunto de palabras de longitud n , y suponga que cadaes la medida equiprobable. Suponga que T (w) = n para todas menos una palabra en cada, y en las palabras excepcionales.
En este ejemplo, T es ciertamente polinomio en entradas típicas, pero T no es polinomio en promedio. T está en GenP .
Ejemplo 2 Mantenga I y como antes, pero defina y . T es polinomio en promedio aunque es exponencial en entradas típicas. T no está en GenP .
En estos dos ejemplos, la complejidad genérica está más estrechamente relacionada con el comportamiento en las entradas típicas que la complejidad promedio de los casos. La complejidad media de los casos mide algo más: el equilibrio entre la frecuencia de los casos difíciles y el grado de dificultad. [21] [22] Hablando en términos generales, un algoritmo que es tiempo polinomial en promedio puede tener solo una fracción subpolinomial de entradas que requieren tiempo superpolinomial para calcular.
Sin embargo, en algunos casos, la complejidad de los casos genérica y promedio son bastante parecidas entre sí. Una función es polinomio en -promedio en esferas si existe tal que dónde es el conjunto inducido por . Si f es polinomio en-promedio en esferas, la f es polinomio en-promedio, y para muchas distribuciones ocurre lo contrario [23]
Teorema 5 [2] Si una función es polinomio en -promedio en esferas, entonces f es genéricamente polinomial en relación con la densidad asintótica esférica.
Teorema 6 [2] Suponga un algoritmo completotiene un límite de tiempo subexponencial T y un algoritmo parcialporque el mismo problema está en ExpGenP con respecto al conjunto correspondiente a una medida de probabilidad en las entradas que para. Entonces hay un algoritmo completo que es-Complejidad de tiempo medio.
Algoritmos heurísticos sin errores
En un artículo de 2006, Bogdanov y Trevisan estuvieron cerca de definir la complejidad de los casos genéricos. [24] En lugar de algoritmos parciales, consideran los denominados algoritmos heurísticos sin errores. Estos son algoritmos completos que pueden fallar si se detienen con la salida "?". La clase AvgnegP se define para constar de todos los algoritmos heurísticos A sin errores que se ejecutan en tiempo polinomial y para los cuales la probabilidad de falla enes insignificante, es decir, converge superpolinomialmente rápido a 0. AvgnegP es un subconjunto de GenP . Los algoritmos heurísticos sin errores son esencialmente los mismos que los algoritmos con fallas benignas definidos por Impagliazzo, donde los algoritmos de tiempo polinómico en promedio se caracterizan en términos de los llamados esquemas de algoritmos benignos.
Referencias
- ^ a b c I. Kapovich, A. Myasnikov, P. Schupp y V. Shpilrain, Complejidad de casos genéricos, problemas de decisión en teoría de grupos y paseos aleatorios , J. Álgebra, vol 264 (2003), 665–694.
- ↑ a b c d e f R. Gilman, AG Miasnikov, AD Myasnikov y A. Ushakov, Generic Case Complexity , primer borrador inédito de un libro, 143 páginas.
- ^ R. Gilman, AG Miasnikov, AD Myasnikov y A. Ushakov, Informe sobre la complejidad de casos genéricos , Herald of Omsk University, Número especial, 2007, 103-110.
- ^ A. Ushakov, disertación , Universidad de la ciudad de Nueva York, 2005.
- ^ R. Gilman, Problemas difíciles en teoría de grupos , charla pronunciada en la Conferencia internacional sobre métodos geométricos y combinatorios en teoría de grupos y teoría de semigrupos, 18 de mayo de 2009.
- ^ I. Kapovich, P. Schupp, V. Shpilrain, Propiedades genéricas del algoritmo de Whiteheads y la rigidez del isomorfismo de grupos aleatorios de un relator , Pacific J. Math. 223 (2006)
- ^ AV Borovik, AG Myasnikov, VN Remeslennikov, Complejidad genérica del problema de conjugación en extensiones HNN y estratificación algorítmica de los grupos de Miller , Internat. J. Álgebra Comput. 17 (2007), 963–997.
- ^ JD Hamkins y A. Miasnikov, El problema de la detención es decidible en un conjunto de probabilidad asintótica uno , Notre Dame J. Formal Logic 47 (2006), 515-524.
- ^ A. Miasnikov y A. Rybalov, Complejidad genérica de problemas indecidibles , Journal of Symbolic Logic 73 (2008), 656–673.
- ↑ A. Rybalov, Sobre la indecidibilidad fuertemente genérica del problema de la detención , Theoret. Computación. Sci. 377 (2007), 268–270.
- ^ MJ Fischer y MO Rabin, Complejidad superexponencial de la aritmética de Presburger , Actas del Simposio SIAM-AMS en Matemáticas Aplicadas 7 (1974) 2741.
- ^ A. Rybalov, Complejidad genérica de la aritmética de Presburger , 356–361 en el Segundo Simposio Internacional sobre Informática en Rusia, CSR 2007, Lecture Notes in Computer Science 4649, Springer 2007.
- ^ R. Gilman, AG Miasnikov, AD Myasnikov y A. Ushakov, Informe sobre la complejidad de casos genéricos, Herald of Omsk University, Número especial, 2007, 103-110.
- ^ AD Myasnikov, Complejidad genérica y funciones unidireccionales , grupos, complejidad y criptografía, 1, (2009), 13–31.
- ^ R. Gilman, AG Miasnikov, AD Myasnikov y A. Ushakov, Nuevos desarrollos en el intercambio de llaves de conmutador , Proc. Primera Int. Conf. sobre Computación Simbólica y Criptografía (SCC-2008), Beijing, 2008.
- ^ AG Myasnikov, V. Shpilrain, A. Ushakov, Un ataque práctico a un protocolo criptográfico basado en grupos de trenzas , en Lecture Notes in Computer Science, 3621, Springer Verlag, 2005, 86–96.
- ^ AD Myasnikov y A. Ushakov, Grupos de trenzado y ataque basados en longitud: criptoanálisis del protocolo de intercambio de claves Anshel-Anshel-Goldfeld , en Criptografía de clave pública PKC 2007, 76-88, Lecture Notes in Comput. Sci., 4450, Springer, Berlín, 2007.
- ^ AG Miasnikov y A. Ushakov, Subgrupos aleatorios y análisis de los ataques basados en la longitud y el cociente , Journal of Mathematical Cryptology, 2 (2008), 29-61.
- ^ A. Miasnikov y A. Rybalov, Complejidad genérica de problemas indecidibles , Journal of Symbolic Logic 73 (2008), 656–673.
- ^ AR Meyer y MS Paterson, ¿Con qué frecuencia son difíciles los problemas aparentemente intratables ? , Informe técnico del MIT, MIT / LCS / TM-126, febrero de 1979.
- ^ Y. Gurevich, El juego de resolución de desafíos: variaciones sobre el tema de P =? NP , Lógica en la columna de informática, The Bulletin of the EATCS, octubre de 1989, p.112-121.
- ^ R. Impagliazzo, Una visión personal de la complejidad del caso promedio , en Actas de la décima Conferencia Anual de Estructura en Teoría de la Complejidad - SCT 1995, IEEE Computer Society, 1995, página 134.
- ^ Y. Gurevich, Completitud de casos promedio , Journal of Computer and System Science, 42 (1991), 346–398.
- ^ A. Bogdanov, L. Trevisan, Complejidad de casos promedio , encontrado. Tendencias Theor. Computación. Sci. 2 , núm. 1, 111 pág. (2006) ..