np完全问题

np完全问题类的,任何的计算问题没有有效的解决方案算法被发现。许多重要的计算机科学问题属于这class-e.g。,旅行商问题,可满足性问题,graph-covering问题。

所谓的简单,或易处理的,可以通过电脑来解决问题算法在运行的多项式时间;即。的问题大小n,时间和数量的步骤是需要找到解决方案多项式的函数n。算法求解困难,或棘手的问题,另一方面,需要时间指数函数问题的大小n。多项式时间算法被认为是有效的,而指数时间算法被认为是低效的,因为后者增长更迅速的执行时间随着问题规模的增加。

yabo亚博网站首页手机大英百科全书测验

数字和数学

一个问题被称为NP (不确定的多项式)如果其解决方案猜想和验证在多项式时间内;不确定性意味着没有特定规则是跟着猜。如果一个问题是NP和所有其他NP问题是多项式时间可约,问题是NP完全的。因此,寻找一种有效的算法对于任何np完全问题意味着一个有效的算法可以发现这样的问题,因为任何问题属于这个类可以改写成任何其他类的成员。尚不清楚是否np完全问题的多项式时间算法会被找到,并确定是否这些问题容易处理棘手的仍是理论中最重要的问题之一计算机科学。当一个np完全问题必须解决,一种方法是使用一个多项式算法近似解;答案从而获得将不一定是最优的但相当接近。