Existe-t-il un algorithme de temps polynomial pour ce problème de décision?

Question

y a-t-il un facteur dans $ m $ c'est $> $ 1 $ $ , mais $ $ M $ ce n'est pas un facteur de $ n $ ?

faux résultat exemple

$ n $ = 8

$ M $ = 16

1, 2, 4, 8, 16

Il n'y a pas d'entier qui n'est pas un facteur de $ n $ qui est $> $ < SPAN CLASS="MATH-CONTENANT"> $ 1 $ Mais << $ M $

Exemple de résultat vrai

$ n $ = 2

$ M $ = 26

1, 2, 13, 26

Il y a un entier 13 $ qui n'est pas un facteur de $ n $ c'est> 1 mais < $ m $

Question

J'ai trouvé une solution pseudo-polynomiale, mais y a-t-il une solution polynomiale pour ce problème dans la longueur de l'entrée?

Answer 1

Ceci est difficile comme le problème d'affacturage entier (prenez simplement $ n $ doit être 2 ou un prime aléatoire qui n'a aucun facteur commun avec $ M $ ).Qu'il y ait un algorithme de temps polynomial pour l'affacturage est un problème ouvert célèbre, mais il est largement convaincu qu'il n'y a probablement aucun algorithme de ce type.