Complejidad de factorización entera

Question

En información cuántica y computación cuántica por Nielsen y Chuang, definen la clase de complejidad np de la siguiente manera (página 142):

Un idioma $ l $ está en np si hay una máquina de Turing $ m $ con las siguientes propiedades.

1. si $ x \ en l $ entonces existe una cadena de testigos $ w $ tal que < Span Class="Math-contenedor"> $ M $ se detiene en el estado $ q_y $ ("Sí Estado") un tiempo polinomial en $ | x | $ cuando la máquina se inicia en el estado $ x $ -blank - $ w $ .
2. si $ x \ no \ in l $ luego para todas las cadenas $ w $ que intenta Juega el papel de un testigo, el La máquina se detiene en estado $ q_n $ ("sin estado") después de un tiempo polinomial en $ | x Cuando $ m $ se inicia en el Estado $ x $ -blank- $ w $ .

Esta definición está motivada por el problema de la decisión de factorización, donde identifican "cadenas de testigos" $ w $ con posibles factores de $ x $ .

Mi confusión es, en función de cómo se definen NP , parece que podemos construir un algoritmo de tiempo polinomial para resolver el problema de la decisión de factoring. Para una cadena determinada $ x $ , inicie la máquina de factoring Turing $ m $ en el estado $ x $ -blank- $ w $ para todos $ w y compruebe si la máquina se detiene en $ q_y $ . Dado que hay $ O (| x |) $ testigos para verificar, y para cada testigo, la máquina se detendrá en el tiempo polinomial, se deduce que este algoritmo determinará si $ x $ tiene factores en el tiempo polinomial.

Claramente, esto no debería funcionar, pero no estoy seguro de dónde está la falla en mi lógica.

Answer 1

El problema es que su algoritmo propuesto es polinomio con respecto al valor numérico de la entrada, pero no en relación con el tamaño de la entrada. La codificación binaria de $ n $ requiere en la mayoría $ \ lceil \ log n \ rceil $ bits, por lo que un algoritmo que toma la codificación de $ n $ y preformas $ \ omega (n) $ Operaciones es en realidad exponencial. Dichos algoritmos se dice que se ejecutan en pseudo polinomio tiempo.

Además, parece que usted está confundiendo la factorización y las pruebas de primaria. Una posible versión de decisión de factoring se da $ (n, x) $ Compruebe si $ n $ tiene un factor $ \ le x $ (mientras que su propuesta se refiere al caso, donde solo se da un $ n $ , y tu bucle para encontrar un factor posible). Mientras se comprueba si se sabe que un número dado se encuentra en $ P $ , se cree que se cree que se encuentra fuera de p.