Existe un polinomio tiempo algoritmo para esta decisión el problema?
-
29-09-2020 - |
Pregunta
Hay un factor en $M$ que es $>$ $1$, pero $<$ $M$ que NO es un factor de $N$?
Resultado Falso Ejemplo
$N$ = 8
$M$ = 16
1, 2, 4, 8, 16
No hay ningún número entero que NO es un factor de $N$ que es $>$ $1$ pero < $M$
Resultado Verdadero Ejemplo
$N$ = 2
$M$ = 26
1, 2, 13, 26
Hay un número entero $13$ que NO es un factor de $N$ que es > 1, pero < $M$
Pregunta
He encontrado un pseudo-polinomial solución, pero existe un polinomio solución para este problema en la longitud de la entrada?
Solución
Esto es difícil como el problema del factoraje entero (simplemente toma $ n $ para ser 2 o un primo aleatorio que no tiene factor en común con $ m $ ).Si hay un algoritmo de tiempo polinomial para factorizar es un problema abierto famoso, pero se cree ampliamente que probablemente no haya tal algoritmo.