complexity-theory - 有界因子 co-NP 吗？

Question

有界因子。

给定数 n，判断它是否有任何小于 k 的适当因数。

这是一个co-Np问题吗？

Answer 1

这个问题确实是一个co-NP问题。为了查看问题是否存在于 co-NP 中，您需要查看是否存在可以否定该问题的多项式验证器。在这种情况下，我们可以陈述 n 的质因数——人们可以很容易地检查它们是否确实是 n 的质因数，以及其中一个因数是否小于 k。如果不是，那么没有任何因子小于 k！这样做，我们证明问题也在 NP 中，因为以同样的方式，我们有一个验证者批准。