是有限因子共NP？

Question

有限因子。

給定數n，決定它是否有任何適當的因子小於k。

這是一個合作Np的問題？

Answer 1

這個問題確實是一個NP問題。 爲了確定問題是否存在於共NP中，您需要查看是否存在可以否定問題的多項式驗證程序。 在這種情況下，我們可以說明n的主要因素 - 人們可以很容易地檢查它們是否確實是n的主要因素，以及其中一個因素是否小於k。如果不是，那麼沒有小於k的因子！ 這樣做，我們證明問題也在NP中，因爲以同樣的方式，我們有一個批准的驗證者。