Demostrar que el problema de la factorización a está en NP

Question

Tratando de poner al día la teoría de la computación, pero no estoy seguro de la solución a esto:

Prove that the problem of factoring α is in NP.

Tengo la sensación de que puede estar relacionado con la búsqueda de un problema NP y la búsqueda de una reducción del problema de la factorización de a.

Answer 1

Esto es simple en realidad. La multiplicación es en P. NP es la misma que "comprobación de todas las posibles soluciones de tamaño polinomio en paralelo". Si alfa se codifica como una longitud de cadena de bits n, los factores de longitud total es, como máximo n + c.

Lo que no se es "NP-completo". No hay ninguna manera de convertir un problema NP arbitraria en la factorización.

Answer 2

Problema en P es un problema, que es computable por determinista de la máquina de Turing en tiempo polinómico Problema de NP es un problema, es thas polynomicaly veryfiable por determinista de la máquina de Turing.

En NP, estamos utilizando no determinismo de tal manera, que se requiere solamente una rama de un árbol de cómputo para ser aceptado (tratamos "todas" las posibilidades en el "mismo" tiempo). medios veryfiable Polynomicaly, que tenemos un certificado (sea esto c), que es una solución a la palabra de entrada (que sea w). El certificado debe ser de una longitud polinómica teniendo en cuenta la longitud de entrada. Nuestra tarea es sólo para verificar si un certificado es una solución. Por ejemplo, en SAT (problema satisfyability) un certificado es una asignacion correcta (que se supuso que no determinista).

Así que probar que su problema está en NP: Existe un DTM que verifica un par (w, c), donde w es el número de entrada y c son sus factores. Tan sólo ha de construir un veryfier que los factores se multiplica en C y lo compara con w.