我们如何知道NP完全问题是NP中最难的？

2

正如其他人已经正确地表明，问题的存在是NP，但不是NP完全意味着P！= NP，所以找到一个会带给你一个永恒的荣耀。一个被认为属于这一类的着名问题是integer factorization。然而，你原来的问题是

不能存在于NP，我们可能尚未发现或证明问题存在，但无法减少到任何NP完全问题？

答案是no。根据NP完备性的定义，问题A为NP完全的两个必要条件之一是每个NP问题都需要在多项式时间内可缩减为A.如果您想了解如何证明每个NP问题可以在多项式时间到一些NP-完全问题时减少，看看Cook-Levin theorem的证明表明3-SAT问题是NP-完全的。这是第一个被证实的NP完全问题，其他许多NP完全问题后来被证明是NP完全的，从3-SAT到这些问题找到适当的减少。

来源

2016-06-01 07:52:25

+0

谢谢！ SAT理念使其完全合情合理。 – rb612

+0

@ rb612欢迎您！ –

1

NP由所有能够（理论上）通过能够做出幸运猜测，猜测解决方案并检查多项式时间解决方案是正确的问题来解决的所有问题。例如，旅行商问题“我可以访问美国所有50个州的首都，行程少于9,825英里”可以通过猜测旅行并检查它不太长而解决。

NP中的一个问题是基本上模拟一个带有各种输入的可编程计算机电路，并检查是否可以实现某个输出。而且这种可编程计算机电路足够强大，可以解决NP中的所有问题。

所以是的，我们知道所有关于NP的所有问题。（那么当然NP完全问题可以用定义来解决NP中的任何问题，如果有问题解决不了，这个问题不在NP中）。

来源

2016-05-31 19:59:57 gnasher729

+0

感谢您的回答。那么，为什么不可能找到NP中的算法X，并且NP完全问题不能简化为X？ – rb612

+0

@ rb612如果在NP中存在问题X但不是NP-Complete，那么NP-Complete是NP的一个真子集。但是，P不能等于NP，因为P中的每个问题都可以用P的多项式时间来约简，所以如果P = NP，NP中的所有问题都必须是NP-Complete（即NP和多项式时间可以减少到彼此）。 – Patrick87

1

除了我们如何知道我们已经发现NP中的每个问题？

我们没有。宇宙中所有问题的集合不仅是无限的，而且是不可数的。

难道不存在我们可能没有发现的问题，或者证明存在于NP中，但不能简化为任何np-complete问题吗？

我们不知道。我们怀疑是这种情况，但这尚未得到证实。如果我们找到一个不是NP完全的NP问题，这将证明P =/= NP。

这是CS中未解决的重大问题之一。许多出色的思想家一直在采取措施，但这个坚果一直是一个棘手的问题。

来源

2016-05-31 20:13:52

+0

太有意思了。你能否解释一点关于找到一个NP不完全的NP问题对P =/= NP来说必然是证明？因为我认为证明P =/= NP的唯一方法是证明没有任何算法能够在确定性多项式时间内解决NP完全问题。 – rb612

+0

@ rb612如果在NP中存在问题X但不是NP-Complete，那么NP-Complete是NP的一个真子集。但是，P不能等于NP，因为P中的每个问题都可以用P的多项式时间来约简，所以如果P = NP，NP中的所有问题都必须是NP-Complete（即NP和多项式时间可以减少到彼此）。 – Patrick87

+0

@ Patrick87谢谢！然而，接受的答案是NP中的所有问题都可以归结为NP完全问题。那么它已经被证明已经或者还是未知数？你能详细说明你的意思吗？“那么P不能等于NP，因为P中的每个问题都是多项式时间可减少到P中的所有其他问题。我没有看到P中每个问题彼此减少如果NP⊂NP-complete，P≠NP。 – rb612

我们如何知道NP完全问题是NP中最难的？

回答

相关问题