結合因子共NPであるか？

Question

結合係数。

与えられた数nが与えられた場合、それがk未満の任意の適切な因子を有するかどうかを決定する。

これは共Npの問題ですか？

Answer 1

問題は確かに共NP問題です。 問題が共NPであるかどうかを調べるには、質問を否定できる多項式検証子があるかどうかを調べる必要があります。 この場合、n - 1の素因数が実際にnの素因数であるかどうか、また因子の1つがkより小さいかどうかを簡単に確認できます。そうでなければ、k未満の因子はありません！ このようにすると、問題はNPにもあることが証明されます。同じように、私たちは承認する検証者を持っているからです。