Una variante de factorización NP-completa.

El libro de Arora y Barak presenta el factoring como el siguiente problema:

$\text{FACTORING} = \{\langle L, U, N \rangle \;|\; (\exists \text{ a prime } p \in \{L, \ldots, U\})[p | N]\}$

Añaden, más adelante en el Capítulo 2, que eliminar el hecho de que $p$ es primo hace que este problema sea NP completo, aunque esto no está relacionado con la dificultad de factorizar números. Parece que puede haber una reducción de SUBSETSUM, pero me quedé atascado al encontrarlo. ¿Alguna mejor suerte por aquí?

EDITAR el 1 de marzo: la recompensa es para la prueba de completitud $NP$ utilizando la reducción determinista de Karp (o Cook).

Esto no es una respuesta, pero está cerca. La siguiente es una prueba de que el problema es NP-duro bajo reducciones aleatorias.

Hay una relación obvia con la suma de subconjuntos que es: supongamos que conoce los factores de : p 1 , p 2 , ... , p k . Ahora, desea encontrar un subconjunto S de p 1 ... p k tal que$N$$p_1$$p_2$$\ldots$$p_k$$S$$p_1$ $\ldots$ $p_k$

El problema al tratar de usar esta idea para mostrar que el problema es NP-hard es que si tienes un problema de suma de subconjuntos con los números , t 2 , ... , t k , no necesariamente puedes encontrar números primos en tiempo polinómico como ese log p i ∝ t i (donde por ∝ , quiero decir aproximadamente proporcional a). Este es un problema real porque, dado que la suma de subconjuntos no está fuertemente completada por NP, necesita encontrar estos log p i para enteros grandes t $t_1$$t_2$$\ldots$$t_k$$\log p_i \propto t_i$$\propto$$\log p_i$$t_i$ .

Ahora, supongamos que necesitamos que todos los enteros ... t k en un problema de suma de subconjuntos estén entre x y x ( 1 + 1 / k ) , y que la suma sea aproximadamente $t_1$ $\ldots$ $t_k$$x$$x(1+1/k)$. El problema de la suma del subconjunto seguirá siendo NP-completo, y cualquier solución será la suma dek/2enteros. Podemos cambiar el problema de números enteros refiere a los reales si dejamos quet ' i estar entretiyTi+$\frac{1}{2}\sum_i t_i$$k/2$$t'_i$$t_i$ , y en lugar de exigir la suma a ser exactamentes, se requiere que sea entresys+$t_i+\frac{1}{10k}$$s$$s$ . Solo necesitamos especificar nuestros números a alrededor de4logkmás bits de precisión para hacer esto. Por lo tanto, si comenzamos con números conbitsBy podemos especificar números realeslogpia aproximadamenteB+4logkbits de precisión, podemos llevar a cabo nuestra reducción.$s + \frac{1}{10}$$4 \log k$$B$$\log p_i$$B + 4 \log k$

Ahora, desde wikipedia (a través de comentario de Hsien-Chih más adelante), el número de primos entre y T + T 5 / 8 es θ ( T 5 / 8 / log T $T$$T+ T^{5/8}$$\theta(T^{5/8}/\log T)$ , así que si usted acaba de elegir números al azar en ese rango, y pruébelos por primalidad, con alta probabilidad de obtener un primo en tiempo polinómico.

Ahora, intentemos la reducción. Digamos que nuestro tiene todos los bits B Si tomamos T i de longitud 3 B trozos, entonces podemos encontrar un número primo p i cerca de T i con 9 / 8 B bits de precisión. Por lo tanto, podemos elegir T i modo que log T i alfa camiseta T i con precisión 9 /$t_i$$B$$T_i$$3B$$p_i$$T_i$$9/8B$$T_i$$\log T_i \propto t_i$ bits Esto nos permite encontrar p i ≈ T i para que log p i ∝ t i con precisión 9 $9/8\, B$$p_i \approx T_i$$\log p_i \propto t_i$ bits Si un subconjunto de estos primos se multiplica por algo cercano al valor objetivo, existe una solución para los problemas de suma del subconjunto original. Entonces dejamos N = Π i p i , elegimos L y U apropiadamente, y tenemos una reducción aleatoria de la suma del subconjunto.$9/8\,B$$N=\Pi_i p_i$$L$$U$

Creo que está vinculado al teorema de PCP (en particular ).$NP = PCP[O(\log{n}), O(1)]$

Un extracto del artículo de Madhu :

... La noción de que un verificador puede realizar cualquier cálculo de tiempo polinómico enriquece considerablemente la clase de teoremas y pruebas y comienza a ofrecer métodos altamente no triviales para probar teoremas. (Una consecuencia inmediata es que podemos asumir que los teoremas / pruebas / aserciones / argumentos son secuencias binarias y lo haremos a partir de ahora). Por ejemplo, supongamos que tenemos una aserción (digamos la hipótesis de Riemann), y decimos que creemos que tiene prueba que cabría en un artículo de 10.000 páginas. La perspectiva computacional dice que dado A y este límite (10,000 páginas), uno puede calcular eficientemente tres enteros positivos N , L , U con L ≤ U ≤ $A$$A$$N, L, U$$L \leq U \leq N$de tal manera que es verdadero si y sólo si N tiene un divisor entre L y U . Los enteros N , L y U serán bastante largos (tal vez escribirlos tomaría un millón de páginas), sin embargo, pueden producirse de manera extremadamente eficiente (en menos de la cantidad de tiempo que le tomaría a una impresora imprimir todos estos enteros, que es, como mucho, un día o dos). (Este ejemplo específico se basa en un resultado debido a Joe Kilian , comunicación personal) ...$A$$N$$L$$U$$N$$L$$U$

... mucho más allá de mis habilidades de teoría de la complejidad :-)

Esta es una idea informal de reducción determinista eficiente (y puede estar incompleta):

Fractran es un lenguaje de programación completo de Turing. Una versión limitada adecuadamente definido de programas Fractran debe ser reducible a la lengua $\{\langle L, U, M \rangle \;|\; (\exists \text{ a positive integer } p \in \{L, \ldots, U\})[p | M]\}$

Por ejemplo, una versión limitada podría preguntar si el entero se produce en la secuencia de salida de un programa Fractran dentro de cierto número de pasos (divisiones) (es decir, M = N j ∗ F i ).$M$$M=N_j * F_i$