complexity-theory - 有界因子はco-NPですか？

Question

有界係数。

数 n が与えられたとき、k より小さい適切な因数があるかどうかを判断します。

これはco-Npの問題ですか？

Answer 1

問題は確かに co-NP 問題です。問題が co-NP にあるかどうかを確認するには、問題を否定できる多項式検証器があるかどうかを確認する必要があります。この場合、n の素因数を述べることができます。それらが実際に n の素因数であるかどうか、および因数の 1 つが k より小さいかどうかを簡単に確認できます。そうでない場合、k より小さい因数はありません。このようにして、問題が NP にもあることを証明します。同じように、承認する検証者がいるからです。