在计算机科学中，什么是“P=NP问题”，为什么它是一个难解问题？

Question

如题所述

Answer 1

P=NP问题是指一类数学问题，其中P代表一类可以用多项式时间内求解的问题，而NP代表另一类用指数时间求解的问题。如果P=NP，则意味着NP实际上可以在多项式时内被求解。这是一个难解问题，因为它会导致以近乎无界的速度求解NP完全问题，而这是目前不可能实现的。

Answer 2

NP问题一直都是信息学的巅峰。巅峰，意即很引人注目但难以解决。在信息学研究中，这是一个耗费了很多时间和精力也没有解决的终极问题，好比物理学中的大统一和数学中的歌德巴赫猜想等。
多数人相信，存在至少一个不可能有多项式级复杂度的算法的NP问题，但是还无法证明。

Answer 3

在计算机科学中，P=NP问题是一个尚未被证明或证伪的猜想，它询问的是：是否可以在多项式时间内解决NP问题？其中，P问题是可以在多项式时间内解决的问题，而NP问题则是可以在多项式时间内验证解的问题。
换言之，如果P=NP，则NP问题的解可以在多项式时间内求解，即NP问题与P问题是等价的，这意味着我们可以在相对较短的时间内解决许多现实世界中非常困难的问题，例如最优化问题、图形问题、加密和密码学等等。因此，P=NP问题被认为是计算机科学中最重要、最具挑战性、最困难的问题之一。
然而，到目前为止，尚未有人能够证明或证伪这个问题。一方面，我们尚未找到任何可以在多项式时间内解决所有NP问题的算法；另一方面，我们也没有找到任何证据表明这样的算法不存在。因此，P=NP问题被认为是计算机科学中最难以解决的问题之一，许多研究人员一直在尝试解决这个问题，并且已经提出了许多有趣的观点和猜想，但目前仍然没有确凿的答案。