La difícil complejidad temporal del generador de permutaciones

Question

Me topé con problemas complicados al calcular la complejidad temporal del algoritmo generador de permutaciones, y tuve grandes dificultades para convencer a un amigo (con experiencia en CS teórica) de la validez de mi razonamiento. Me gustaría aclarar esto aquí.

Cuestión de complejidad difícil Dado un número entero positivo $n$ ¿cuál es la complejidad temporal de generar todas las permutaciones en el conjunto $[n]=\{1,2,..,n\}$ ?

Razonamiento del amigo Cualquier algoritmo para generar todas las permutaciones de $[n]$ toma $\Omega(n!)$ tiempo. Este es un límite inferior super-exponencial demostrable, [editado ]por lo que el problema está en EXPTIME.

Mi razonamiento El razonamiento anterior es correcto, salvo que hay que calcular la complejidad con respecto a el número de bits de salida previstos . En este caso, esperamos $n!$ números en la salida, y cada uno puede ser codificado en $\log n$ bits; por lo tanto, esperamos que $b=O(n!\log n)$ bits de salida. Un algoritmo estándar para recorrer todos los $n!$ permutaciones tendrá una sobrecarga de tiempo polinómica, es decir, se ejecutará en $s(n)=O(n!n^k)$ tiempo, por lo que necesitaremos $t(n)=b(n)+s(n) = O(n!(\log n + n^k)) $ tiempo en total.

Desde $b(n)$ es el número de bits de salida, expresaremos $t(n)$ en función de $b(n)$ . Para ello, tenga en cuenta que $n^k \approx (n!)^{k/n}$ utilizando $n! \approx n^n$ Así que $s(n)=O( b(n) (b(n))^{k/n}) = O(b^2(n) )$ . Por lo tanto, tenemos un algoritmo de tiempo polinómico en el número de bits de salida, y el problema debería estar en $P$ no en, digamos, EXPTIME.

Pregunta principal : ¿El razonamiento de quién es correcto, si es que lo es?

Nota Planteé este problema aquí porque tuve una mala experiencia en StackOverflow con un problema diferente de complejidad temporal difícil; y esto ciertamente no es adecuado para Cstheory.SE ya que no es de nivel de investigación.

Answer 1

A la hora de clasificar los problemas, no se clasifican en función del tamaño de la salida, en bits, sino del tamaño de la entrada. El tamaño de la entrada es el tamaño del problema, que es el que nos importa al definir las clases de complejidad estándar. Los problemas en P requieren un tiempo limitado por una función polinómica del tamaño del problema. Los problemas en P-SPACE ocupan un espacio limitado por una función polinómica del tamaño del problema. Los problemas en E requieren un tiempo limitado por una función exponencial del tamaño del problema, y así sucesivamente. Si el tamaño de la salida es exponencial en el tamaño del problema de entrada, (que, en este caso sería el conjunto inicial), entonces está claro que el problema debe ser, como mínimo, exponencial.

Si quieres definir tu propia clasificación de problemas (POUT-TIME y POUT-SPACE o algo así) en función del tamaño de la salida, eres bienvenido, pero no es así como se definen las clases de complejidad estándar. Su amigo tiene razón.

Answer 2

Deseo refinar sustancialmente la respuesta de Keith Irwin como sigue.

Dada una clase de problemas $\mathcal{P}$ La solución de cada uno de ellos puede calcularse en un tiempo polinómico en el tamaño de sus entradas. Esto hace no significa que $\mathcal{P}$ se encuentra en la clase de complejidad $\mathsf{P}$ . ¿Por qué no? Porque $\mathsf{P}$ admite sólo problemas de decisión

Por ejemplo, supongamos que $\mathcal{P}$ es aquella clase de problemas que proporciona como entrada un entero positivo $n$ y pide el valor de $n+1$ como salida. Es fácil ver que $\mathcal{P}$ puede resolverse en tiempo polinómico en el tamaño de la entrada. Pero $\mathcal{P} \not \subset \mathsf{P}$ , para $\mathcal{P}$ no consiste en absoluto en problemas de decisión. En cambio, $\mathcal{P}$ es un conjunto de problemas de funcionamiento ; se encuentra en $\mathsf{FP}$ , esa clase de funciones computables en poli tiempo.

Del mismo modo, el generador de permutaciones toma la entrada $n$ y proporciona una función $f(n)$ como salida; no decidir cualquier cosa. Por lo tanto, independientemente de su complejidad, no pertenece a $\mathsf{P}$ . Es más significativo pensar en el problema de generación de permutaciones como un problema de funciones. El límite superexponencial demostrable mencionado en la pregunta impide que el problema de generación esté en $\mathsf{FP}$ . Quizás $\mathsf{FEXP}$ sería una mejor respuesta, aunque no estoy seguro. Como dijo Keith, utilizar el número de bits de salida como medida de la complejidad requiere nuevas definiciones de las clases de complejidad que tengan en cuenta el tamaño de la salida.

Tenga en cuenta que es ciertamente significativo hacer versiones de decisión del problema de generación de permutaciones, como:

Dados los enteros $(n,k)$ ¿Qué es el $k$ -ésimo bit de la salida del generador de permutaciones en $[n]$ ?

Este problema en particular está en $\mathsf{P}$ para el $k$ puede ser calculado por medio de un eficiente permutación unranking .

Answer 3

La atadura de tu amigo es bastante débil. Dejemos que el número de entrada sea $x$ . Entonces la salida es $x!$ permutaciones, pero la longitud de cada permutación no es $x$ bits, como usted afirma, pero $\Theta(\lg(x!)) = \Theta(x \lg x)$ bits. Por lo tanto, la longitud total de salida es $\Theta(x! \;x \lg x)$ bits.

Pero, como ya ha señalado @KeithIrwin, las clases de complejidad funcionan en función del tamaño de la entrada. Una entrada valor de $x$ tiene tamaño $n=\lg x$ , por lo que la generación es $\Omega(2^n! \;2^n n)$ .

Answer 4

En el análisis de los algoritmos hay diferentes modelos de costes .

Los más comunes son (cita de Wikipedia):

• el modelo de coste uniforme, también llamado medición de coste uniforme (y variaciones similares), asigna un coste constante a cada máquina operación de la máquina, independientemente del tamaño de los números implicados
• el modelo de coste logarítmico, también llamado medición de coste logarítmico (y sus variaciones), asigna un coste a cada operación de la máquina proporcional al número de bits implicados

Supongo que las complejidades que diste utilizan un modelo diferente y por lo tanto no se pueden comparar, ambas pueden ser correctas.