什么是计算机科学中的NP-complete?
收藏

什么是NP完全问题?为什么它在计算机科学中如此重要?

最佳答案

NP代表非确定性多项式时间。

这意味着可以使用非确定性图灵机(类似于常规图灵机,但还包括非确定性“选择”功能)在多项式时间内解决问题。基本上,解决方案必须可以在聚合时间内进行测试。如果是这样,并且可以使用修改后的输入使用给定问题来解决已知的NP问题(可以将NP问题简化为给定问题),则该问题是NP完全的。

要摆脱NP完全问题,最主要的事情是它不能以任何已知的方式在多项式时间内求解。 NP-Hard / NP-Complete是一种显示某些类型的问题在现实时间内无法解决的方法。

编辑:正如其他人指出的那样,通常有NP-完全问题的近似解。在这种情况下,逼近解通常使用特殊符号给出逼近界,该逼近告诉我们逼近的接近程度。

    公众号
    关注公众号订阅更多技术干货!