是否存在该决策问题的多项式时间算法？

Question

是 $ m $ 的一个因素，即 $> $ $ 1 $ ，但 $ <$ $ m $ 不是a $ n $ ？

的因子

false结果示例

$ n $ = 8

$ m $ = 16

1,2,4,8,16

没有整数不是 $ n $ $> $ <跨越类=“math-container”> $ 1 $ 但< $ m $

true结果示例

$ n $ = 2

$ m $ = 26

1,2,13,26

有一个整数 $ 13 $ ，它不是 $ n $ 的一个因子> 1但< $ m $

问题

我发现了一个伪多项式解决方案，但是在输入的长度中存在该问题的多项式解决方案？

Answer 1

这很难作为整数因子问题（只需使用 $ n $ 为2或无随机素数，这些素材与 $ M $ ）。是否存在用于分解的多项式时间算法是着名的开放问题，但众所周知，很可能没有这样的算法。