Complejidad de casos genéricos

Sea I un conjunto infinito de entradas para un problema computacional.

Definición 1. Una función de tamaño en I es un mapa${\displaystyle \sigma :I\to \mathbb {N} }$con alcance infinito. La bola de radio n es${\displaystyle B_{n}=\{x\in I\mid \sigma (x)\leq n\}}$.

Si las entradas están codificadas como cadenas sobre un alfabeto finito, el tamaño podría ser la longitud de la cadena.

Dejar${\displaystyle \{\mu _{n}\}}$ser un conjunto de distribuciones de probabilidad donde${\displaystyle \mu _{n}}$es una distribución de probabilidad en${\displaystyle B_{n}}$Si las bolas${\displaystyle B_{n}}$son finitos, entonces cada${\displaystyle \mu _{n}}$puede tomarse como la distribución equiprobable, que es el caso más común. Nótese que solo un número finito de${\displaystyle B_{n}}$'s pueden estar vacíos o tener${\displaystyle \mu _{n}(B_{n})=0}$; los ignoramos.

Definición 2. La densidad asintótica de un subconjunto${\displaystyle X\subset I}$es${\displaystyle \rho (X)=\lim _{n\to \infty }\mu _{n}(X\cap B_{n})}$cuando existe este límite.

Cuando las bolas${\displaystyle B_{n}}$son finitos y${\displaystyle \mu _{n}}$es la medida equiprobable,

${\displaystyle \rho (X)=\lim {\frac {|X\cap B_{n}|}{|B_{n}|}}.}$

En este caso, suele ser conveniente utilizar esferas.${\displaystyle I_{n}=\{x\in I\mid \sigma (x)=n\}}$en lugar de bolas y definir${\displaystyle \rho '(X)=\lim {\frac {|X\cap I_{n}|}{|I_{n}|}}}$Un argumento que utiliza el teorema de Stolz muestra que${\displaystyle \rho (X)}$existe si${\displaystyle \rho '(X)}$Sí, y en ese caso son iguales.

Definición 3${\displaystyle X\subsetequ I}$es genérico si${\displaystyle \rho (X)=1}$y insignificante si${\displaystyle \rho (X)=0}$. 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 cuán rápido${\displaystyle \mu _{n}(X\cap B_{n})}$converge a 1. La convergencia superpolinómica parece ser suficientemente rápida.

Definición 4 Un algoritmo pertenece a GenP (tiempo genérico polinomial) si nunca da respuestas incorrectas y si da respuestas correctas en tiempo polinomial sobre un conjunto genérico de entradas. Un problema pertenece a GenP si admite un algoritmo en GenP . Lo mismo ocurre con GenL ( tiempo genérico lineal ), GenE ( tiempo genérico exponencial con exponente lineal), GenExp (tiempo genérico exponencial), etc. ExpGenP es la subclase de GenP para la cual el conjunto genérico relevante es exponencialmente genérico.

De manera más general para cualquier${\displaystyle f:\mathbb {N} \to \mathbb {N} }$Podemos definir la clase Gen(f) correspondiente a una complejidad temporal O ( f ) en un conjunto genérico de entradas.

Definición 5. Un algoritmo resuelve un problema de forma genérica si nunca da respuestas incorrectas y si da respuestas correctas para un conjunto genérico de entradas. Un problema es genéricamente resoluble si algún algoritmo lo resuelve de forma genérica.

• Los famosos problemas indecidibles : bajo hipótesis adecuadas, los problemas de decisión de palabra, conjugación y pertenencia son genéricamente polinomiales. ^{[ 1 ]}
• Los problemas de búsqueda de palabras y conjugaciones están en GenP para todos los grupos finitamente presentados fijos. ^{[ 4 ]}

• El conocido procedimiento de enumeración de clases laterales admite una cota superior computable en un conjunto genérico de entradas. ^{[ 5 ]}

• El algoritmo de Whitehead para comprobar si un elemento de un grupo libre se mapea a otro mediante un automorfismo tiene un límite superior exponencial en el peor de los casos, pero funciona bien en la práctica. Se demuestra que el algoritmo pertenece a GenL . ^{[ 6 ]}
• El problema de conjugación en las extensiones HNN puede ser irresoluble incluso para grupos libres . Sin embargo, su complejidad computacional es cúbica. ^{[ 7 ]}

• El problema de parada para la máquina de Turing con cinta de una sola cara es fácilmente decidible la mayor parte del tiempo; está en GenP ^{[ 8 ].}

Se desconoce la situación para la cinta de doble cara. Sin embargo, existe una especie de límite inferior para máquinas de ambos tipos. El problema de parada no está en ExpGenP para ningún modelo de máquina de Turing, ^{[ 9 ] [ 10 ]}

• El problema de correspondencia de Post está en ExpGenP . ^{[ 2 ]}

El problema de decisión para la aritmética de Presburger admite una cota inferior en el peor caso de doble exponencial ^{[ 11 ]} y una cota superior en el peor caso de triple exponencial. Se desconoce la complejidad genérica, pero se sabe que el problema no pertenece a ExpGenP . ^{[ 12 ]}

Como es bien sabido que los problemas NP-completos pueden ser fáciles en promedio, no sorprende que varios de ellos también lo sean en general.

• El problema de satisfacibilidad triple se encuentra en ExpGenP . ^{[ 13 ]}
• El problema de la suma de subconjuntos está en GenP . ^{[ 2 ]}

Existe una versión de complejidad genérica de una función unidireccional ^{[ 14 ]} que produce la misma clase de funciones, pero permite considerar supuestos de seguridad diferentes a los habituales.

Una serie de artículos ^{[ 15 ] [ 16 ] [ 17 ]} se dedica al criptoanálisis del protocolo de intercambio de claves Anshel-Anshel-Goldfeld , cuya seguridad se basa en supuestos sobre el grupo de trenzas . 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 bajo las cuales funciona. El punto de vista genérico también sugiere un nuevo tipo de ataque llamado ataque de cociente y una versión más segura del protocolo Anshel-Anshel-Goldfeld.

• Un famoso teorema de Rice establece que si F es un subconjunto del conjunto de funciones computables parciales de${\displaystyle \mathbb {N} }$a${\displaystyle \{0,1\}}$Entonces, a menos que F o su complemento sean vacíos, el problema de decidir si una máquina de Turing particular calcula o no una función en F es indecidible. El siguiente teorema ofrece una versión genérica.

Teorema 1 ^{[ 19 ]} Sea I el conjunto de todas las máquinas de Turing. Si F es un subconjunto del conjunto de todas las funciones computables parciales de${\displaystyle \mathbb {N} }$Si I es un conjunto exponencialmente genérico de I , de modo que F y su complemento no sean vacíos, entonces el problema de decidir si una máquina de Turing dada calcula o no una función a partir de F no es decidible en ningún subconjunto exponencialmente genérico de I.

• Los siguientes teoremas provienen 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éricas. Más precisamente, para una función de complejidad propia f ,${\displaystyle Gen(f)\subsetneq Gen(f^{3})}$.

El siguiente teorema demuestra que, así como existen problemas completos en el caso promedio dentro de los problemas NP distribucionales, también existen problemas completos en el caso genérico. Los argumentos en el caso genérico son similares a los del caso promedio, y el problema completo en el caso genérico también es completo en el caso promedio. Se trata del problema de parada acotada distribucional .

Teorema 4 ^{[ 2 ]} Existe una noción de reducción genérica en tiempo polinomial con respecto a la cual el problema de parada acotada distribucional es completo dentro de la clase de problemas NP distribucionales.

Meyer y Paterson ^{[ 20 ]} definen un algoritmo como de tiempo casi polinomial, o APT, si se detiene en p(n) pasos para 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 NP-completos en GenP , pero Meyer y Paterson muestran que este no es el caso para APT. Demuestran que un problema NP-completo es reducible a un problema en APT si y solo si P = NP . Por lo tanto, APT parece mucho más restrictivo que GenP .

La complejidad genérica es similar a la complejidad promedio . Sin embargo, existen diferencias significativas. La complejidad genérica mide directamente el rendimiento de un algoritmo en la mayoría de las entradas, mientras que la complejidad promedio mide el equilibrio entre instancias fáciles y difíciles. Además, la complejidad genérica se aplica naturalmente a problemas indecidibles .

Suponer${\displaystyle {\mathcal {A}}}$es un algoritmo cuya complejidad temporal ,${\displaystyle T:I\to \mathbb {N} }$es polinomial en${\displaystyle \mu }$promedio. ¿Qué podemos inferir sobre el comportamiento de${\displaystyle {\mathcal {A}}}$¿Con entradas típicas?

Ejemplo 1 Sea I el conjunto de todas las palabras sobre${\displaystyle \{0,1\}}$y definir el tamaño${\displaystyle \sigma (w)}$tener la longitud de una palabra, ${\displaystyle |w|}$. Definir${\displaystyle I_{n}}$sea ​​el conjunto de palabras de longitud n , y supongamos que cada${\displaystyle \mu _{n}}$es la medida equiprobable. Supongamos que T(w)=n para todas las palabras excepto una en cada${\displaystyle I_{n}}$, y${\displaystyle T(w)=2^{2^{n}}}$sobre palabras excepcionales.

En este ejemplo, T es ciertamente polinomial en entradas típicas, pero T no es polinomial en promedio. T está en GenP .

Ejemplo 2 Mantén yo y${\displaystyle \sigma (w)=|w|}$como antes, pero define${\displaystyle \mu (w)=2^{-2|w|-1}}$y ${\displaystyle T(w)=2^{|w|}}$. T es polinomial 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 relacionada con el comportamiento en entradas típicas que con la complejidad del caso promedio. La complejidad del caso promedio mide otra cosa: el equilibrio entre la frecuencia de instancias difíciles y el grado de dificultad. ^{[ 21 ] [ 22 ]} En términos generales, un algoritmo que es polinomial en tiempo promedio puede tener solo una fracción subpolinomial de entradas que requieren un tiempo superpolinomial para su cálculo.

Sin embargo, en algunos casos, la complejidad genérica y la complejidad promedio son bastante similares. Una función${\displaystyle f:I\rightarrow \mathbb {R} ^{+}}$es polinomial en${\displaystyle \mu }$-promedio en esferas si existe${\displaystyle k\geq 1}$de tal manera que${\displaystyle \sum _{w\in I_{n}}f^{1/k}(w)\mu _{n}(w)=O(n)}$dónde${\displaystyle \{\mu _{n}\}}$ es el conjunto inducido por${\displaystyle \mu }$. Si f es un polinomio en${\displaystyle \mu }$-promedio en esferas, la f es polinómica en${\displaystyle \mu }$-promedio, y para muchas distribuciones se cumple lo contrario ^{[ 23 ]}

Teorema 5 ^{[ 2 ]} Si una función${\displaystyle f:I\rightarrow \mathbb {R} ^{+}}$es polinomial en${\displaystyle \mu }$-promedio en esferas entonces f es genéricamente polinomial en relación con la densidad asintótica esférica${\displaystyle \rho '}$.

Teorema 6 ^{[ 2 ]} Supongamos que existe un algoritmo completo${\displaystyle {\mathcal {A}}}$tiene un límite de tiempo subexponencial T y un algoritmo parcial${\displaystyle {\mathcal {B}}}$ para el mismo problema está en ExpGenP con respecto al conjunto${\displaystyle \{\mu _{n}\}}$correspondiente a una medida de probabilidad${\displaystyle \mu }$ en las entradas que para${\displaystyle {\mathcal {A}}}$. Luego hay un algoritmo completo que es${\displaystyle \mu }$-complejidad temporal promedio.

En un artículo de 2006, Bogdanov y Trevisan estuvieron cerca de definir la complejidad genérica de casos. ^{[ 24 ]} En lugar de algoritmos parciales, consideran los llamados algoritmos heurísticos sin errores. Estos son algoritmos completos que pueden fallar deteniéndose con la salida "?". La clase AvgnegP se define para consistir en todos los algoritmos heurísticos sin errores A que se ejecutan en tiempo polinomial y para los cuales la probabilidad de falla en${\displaystyle I_{n}}$es 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 fallos benignos definidos por Impagliazzo, donde los algoritmos de tiempo polinomial en promedio se caracterizan en términos de los llamados esquemas de algoritmos benignos.