2
A
答えて
2
問題は確かに共NP問題です。 問題が共NPであるかどうかを調べるには、質問を否定できる多項式検証子があるかどうかを調べる必要があります。 この場合、n - 1の素因数が実際にnの素因数であるかどうか、また因子の1つがkより小さいかどうかを簡単に確認できます。そうでなければ、k未満の因子はありません! このようにすると、問題はNPにもあることが証明されます。同じように、私たちは承認する検証者を持っているからです。
関連する問題
- 1. 左結合演算子対右結合演算子
- 2. '分' 因子
- 3. 因子x軸
- 4. 演算子結合性