¿Por qué no tomar la representación unaria de números en algoritmos numéricos?

Un algoritmo de tiempo pseudo-polinomial es un algoritmo que tiene tiempo de ejecución polinomial en el valor de entrada (magnitud) pero tiempo de ejecución exponencial en el tamaño de entrada (número de bits).

Por ejemplo, probar si un número $n$ es primo o no, requiere un ciclo a través de los números del 2 al $n-1$ y verificar si $n$ mod $i$ es cero o no. Si el mod tarda O (1) tiempo, la complejidad del tiempo general será O (n).

Pero si dejamos que sea ​​el número de bits necesarios para escribir la entrada, entonces x = log n (binario), entonces n = 2 x y el tiempo de ejecución del problema será O ( 2 x ), que es exponencial.$x$$x = \log n$$n = 2^x$$2^x$

Mi pregunta es, si consideramos la representación unaria de la entrada , entonces siempre x = ny luego el tiempo pseudo-polinomial será igual a la complejidad del tiempo polinomial. Entonces, ¿por qué nunca hacemos esto?$n$$x=n$

Además, dado que existe un algoritmo de tiempo pseudo-polinomial para la mochila, tomando , la mochila será polinómica como resultado P = NP$x=n$

Lo que esto significa es que la mochila unaria está en P. No significa que la mochila (con números codificados en binario) esté en P.

Se sabe que la mochila es NP-completa. Si mostraras que la mochila está en P, eso mostraría que P = NP.

Pero no ha demostrado que la mochila está en P. Ha demostrado que la mochila unaria está en P. Sin embargo, no se sabe que la mochila unaria sea NP-completa (de hecho, la sospecha estándar es que probablemente no sea NP-complete ) Por lo tanto, poner una mochila unaria en P no implica que P = NP.

Entonces, ¿qué problema debería importarnos más, la mochila o la mochila unaria? Si su motivación se basa en preocupaciones prácticas, entonces la respuesta dependerá del tamaño de los números para los que desea resolver el problema de la mochila: si son grandes, entonces ciertamente le importa más la mochila que la mochila unaria. Si su motivación se basa en preocupaciones teóricas, entonces la mochila es posiblemente más interesante, ya que nos permite obtener una comprensión más profunda, nos permite hacer una distinción entre tamaño y magnitud, mientras que la mochila unitaria nos impide hacer esa distinción.

Para responder la pregunta de seguimiento sobre el algoritmo de programación dinámica para el problema de la mochila:

Sí, el mismo algoritmo de programación dinámica se puede aplicar tanto a las mochilas como a las mochilas unarias. Su tiempo de ejecución es polinomial en la magnitud de los números, pero exponencial (no polinomial) en la longitud de los números cuando se codifica en binario. Por lo tanto, su tiempo de ejecución es polinómico en la longitud de la entrada cuando la entrada está codificada en unario, pero no es polinomial en la longitud de la entrada cuando la entrada está codificada en binario. Es por eso que hacemos consideran este algoritmo de programación dinámica para ser un algoritmo de tiempo polinómico para la mochila unario, pero no consideramos que sea un algoritmo de tiempo polinómico para la mochila (codificación binaria).

Recuerde que decimos que un algoritmo se ejecuta en tiempo polinómico si su tiempo de ejecución es como máximo algún polinomio de la longitud de la entrada, en bits .

Añadiría una pequeña cosa a la respuesta de DW:

He visto personas que piensan que debido a que la mochila unaria está en P, por lo tanto, podemos usarla en lugar de la mochila cuyos mejores algoritmos actuales tienen un tiempo exponencial.

Deje que la entrada sea y k y considerar el algoritmo de programación dinámica para la mochila y la mochila unario. El tiempo de ejecución para ambos es O ( n k ) . Es el mismo tiempo de ejecución. Es decir, si tiene una entrada, no importará si utiliza la programación dinámica para la mochila unaria o la programación dinámica para la mochila. Ambos tomarán (aproximadamente) la misma cantidad de tiempo para resolver la instancia del problema. Teóricamente, en cualquier lugar donde use uno, también puede usar el otro. Solo necesita convertir números de unario a binario y viceversa.$W=\{w_1, \ldots, w_n\}$$k$$O(nk)$

$O(nk)$

Si le preocupa un problema de forma aislada, puede hacerlo. En realidad, eso es lo que a menudo hacen las personas en algoritmos. La complejidad de los algoritmos gráficos a menudo se expresa en términos de la cantidad de vértices y la cantidad de aristas, no del tamaño de la cadena que los codifica.

Pero esto es solo cuando estamos lidiando con un problema aislado. No es útil cuando se trata de problemas con diferentes tipos de entradas. Para los gráficos podemos hablar sobre el tiempo de ejecución wrt para el número de vértices y bordes. Para la mochila podemos hablar sobre la cantidad de artículos y el tamaño de la mochila. Pero, ¿y si queremos hablar de ambos? Por ejemplo, cuando queremos reducciones entre problemas, o discutir una clase de problemas que incluye problemas arbitrarios, no solo aquellos con un gráfico como entrada. Necesitamos un parámetro universal de entradas. Una entrada en general es solo una cadena, somos nosotros quienes interpretamos sus símbolos como números unarios, números binarios, gráficos, etc. Para desarrollar una teoría general de la complejidad del algoritmo y los problemas, necesitamos un parámetro general de las entradas. El tamaño de la entrada es una opción obvia y resulta ser lo suficientemente robusta como para que podamos construir una teoría razonable sobre ella. No es la única posibilidad. Para uno artificial podemos construir una teoría basada en$2$

$k$$100$$100$$k$$2^{100}-1$$k$$k$$2^{100}-1$

$n$$n$$p(n)$$k$$p(n)$$k$$2^{p(n)}-1$$k$$k$

$n$$k$

En resumen y simple, te mostraré por qué.

Supongamos que tiene un algoritmo de factorización. Excepto por la pequeña diferencia de que uno acepta enteros para la entrada y el otro$Tally$. Como puede ver, ambos fragmentos de código son similares.

x = input integer

factors = [];

for i in range(1, x + 1):
    if x % i == 0:
     factors.append(i)

 print(factors)

Observe que el algoritmo anterior es polinomial del valor numérico de $x$. Tomará$x$cantidad de pasos en el bucle. Pero cuando se trata del tamaño de bits, en realidad$O(2^n)$.

Supongamos que hago una pequeña edición del código que tomará $Tally/Unary$. Ahora será$O(n)$ tiempo en valor y longitud de la entrada $x$.

x = input tallies

factors = [];

for i in range(1, x + 1):
    if x % i == 0:
     factors.append(i)

 print(factors)

La representación de entrada no hace que el código se ejecute más rápido. A pesar de que el segundo algoritmo es realmente poli-tiempo. No es muy práctico para encontrar los factores de RSA.