Reducir el problema de factorización entera a un problema de NP-completado

Question

Estoy luchando por comprender la relación entre NP-intermedio y NP-complete. Sé que si P! = NP basado en el teorema de Ladner existe una clase de idiomas en NP pero no en P o en NP-Complete. Todos los problemas en NP pueden reducirse a un problema completado de NP, sin embargo, no he visto ningún ejemplo para reducir un problema sospechoso de NPI (como la factorización entera) en un problema completado de NP. ¿Alguien sabe de algún ejemplo de esta u otra reducción NPI-> NPC?

Answer 1

Por ejemplo, hay una reducción clásica ordenada de factoring a SAT, que también es una fuente de presuntas instancias de SAT "difíciles". Básicamente, uno usa ideas EE para la multiplicación binaria codificada en el circuito SAT. Piense en la multiplicación binaria como una adición de una serie de multiplicandos desplazados izquierdo, cada uno "enmascarado" (yed) por los bits de un multiplicador. Las adiciones se pueden realizar mediante un circuito de adición binario que es una serie de adherentes completos.

Un talentoso universitario podría construir este algoritmo. No sé dónde se propuso o implementó por primera vez en la literatura. Me interesaría escuchar cualquier referencia.

Ver EG Satisfacer esto: un intento de resolver la factorización prima utilizando solucionadores de satisfacción de Stefan Schoenmackers y Anna Cavender que lo pone en detalle. También el DiMacs SAT Challenge A partir de finales de los 90, tuvieron casos de factorización generados por algunos investigadores, pero posiblemente el algoritmo no fue escrito por separado en un documento durante esa época.

Answer 2

Para ser absolutamente clara, no se sabe que la factorización entera sea intermedia NP, solo se sospecha que se basa en la falta de prueba de completidad de NP o algoritmo de tiempo polinómico (a pesar de mucho trabajo en ambos). No conozco ningún problema natural (es decir, no construido por Ladner para la prueba) que definitivamente es NP-intermedio si P y NP son diferentes.

Bien, después de ese descargo de responsabilidad, Gráfico isomorfismo es otro candidato probable para un problema natural intermedio NP. Hay una simple reducción de tiempo polinómico a Subgraph isomorfismo - ¡Solo deja los gráficos de la misma manera! El isomorfismo gráfico es solo el caso especial del isomorfismo del subgrafio donde ambos gráficos tienen el mismo tamaño. El toque final es que el subgraph isomorfismo es NP-COMPLETO.

Aparte de eso, siempre existe la reducción no tan informativa prometida por el Teorema de Cook-Levin, sabemos que cualquier problema intermedio de NP tiene una máquina de Turing de tiempo polinomial no determinista que lo decide, y podemos convertir esto en una instancia de SAT (¡solo tenemos que construir el TM!).