我正在学习如何证明某些问题属于NP。在Thomas Cormen的算法导论中,他指出,如果给定一个问题的解决方案,您可以在多项式时间内验证其正确性,则该问题属于NP。
比如说,问题是2x + 9 = 55,假设我不知道找到正确的x值需要多长时间,但是一个算法返回了解23。那么,要证明它属于NP,我只需要将23代入方程中,看看这是否需要多项式时间并且得到了55。谢谢。
比如说,问题是2x + 9 = 55,假设我不知道找到正确的x值需要多长时间,但是一个算法返回了解23。那么,要证明它属于NP,我只需要将23代入方程中,看看这是否需要多项式时间并且得到了55。谢谢。