一応専門家の端くれですが、少なくとも私の周りでは 素因数分解はPではないと思われています。 でも、NP-complete（決定問題の場合ね）でもないと思われています。 じゃあ結局どこに入るのだといいますと、その中間のクラス。 P≠NP　が成立するならば、その中間クラスが存在することがすぐに 言えますので、素因数分解は…