NP-Hard解问题

Question

我有NP难题。假设我找到了一些多项式算法，它只找到该问题许多现有解决方案中的一个，但至少有一个解决方案(如果在问题中存在)。该算法是否被认为是NP=P问题的解决方案(如果该算法转化为数学证明)？

感谢您的回答

Answer 1

NP是一类决策问题。你的算法应该对所有可能的情况(问题)正确地回答“是”或“否”。

例如，这个问题：“给定图G和数k，G是否包含一个大小为>= k的团”是NP-困难的。如果你有一个多项式时间算法，每次都能正确回答“是”或“否”，那么它就是P=NP的有效证明。如果对所有可能的G和k都存在，则该算法不需要显式地显示仅有集团的答案。

Answer 2

如果您发现了一个NP-hard问题，并且您可以检测到一些可以在多项式时间内解决的案例(将其他案例留给指数时间)，那么只有当剩余案例的分数在log(N)/N的数量级时，您才会更改整个问题的顺序，而且即使到那时，您也只能将指数型案例限制为只检查log(N)而不是所有N种可能性。

此外，如果你发现一个NP-hard问题，你认为你可以在多项式时间内解决所有情况，那么你可能犯了一个错误，要么正确地提出了一个NP-hard问题，要么找到了更麻烦的例子。在相信自己之前，先尝试更大的测试集！