有界因子是co-NP吗？
有界因子。
给定数字n，判断它是否有小于k的真因数。
这是一个 co-Np 问题吗？
Bounded Factor.
Given number n, decide whether it has any proper factor less than k.
Is this a co-Np problem?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
该问题确实是一个co-NP问题。
为了查看 co-NP 中是否存在问题，您需要查看是否存在可以否定该问题的多项式验证器。
在这种情况下，我们可以陈述 n 的质因数 - 人们可以轻松检查它们是否确实是 n 的质因数，以及其中一个因数是否小于 k。如果不是，则没有小于 k 的因数！
这样做，我们证明问题也是NP的，因为同样的，我们有一个批准的验证者。
The problem is indeed a co-NP problem.
In order to see if a problem is in co-NP, you need to see if there is a polynomial verifier that could negate the question.
In this case, we could state the prime factors of n - one could easily check if they are indeed n's prime factors, as well as if one of the factors is smaller than k. If not, then there is no factor less than k!
Doing it this way, we prove that the problem is also in NP, because in the same way, we have a verifier that approves.