这是我在这个网站上的第一个问题。
我最近正在研究NP。我对此主题有些困惑，想提出我的推论并验证我。
I）每个NP问题都可以在指数时间内解决。
II）如果P ＝ NP，则NP ＝ NP完全。
III）分解为2个素数因子的问题是NP。
IV）如果问题X可以简化为已知的NP-HARD问题，则X必须是NP-HARD。
任何人都可以验证我的推论并了解我？
I）每个NP问题都可以在指数时间内解决。
是的，这是因为它可以在非确定性机器（NP的定义）上在多项式时间内求解，因此可以在确定性机器上以指数时间求解。
II）如果P ＝ NP，则NP ＝ NP完全。
是的，因为如果P = NP，则所有NP问题的“是”和“否”答案都相当容易实现，因此针对“是”问题运行多项式时间算法，然后像这样回答。假设存在这样的多项式时间机器，结果总是正确的，并且以多项式时间运行。
III）分解为2个素数因子的问题是NP。
是的。给定一个数字及其素因分解-可以很容易地验证这是否是正确的答案（这是NP中问题的等效定义）。
IV）如果问题X可以简化为已知的NP-HARD问题，则X必须是NP-HARD。
不，应该相反。您需要将一个已知的NP-Hard问题简化为X，然后可以将X标记为NP-Hard。
记住NP中的每个问题都会归结为SAT（Cook Levin定理），而P！= NP-Complete（或者至少我们认为）
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句