我对NP-hard问题感到困惑。
一些NP-hard问题属于NP类,被称为NP-Complete问题,而另一些则不属于NP类。
例如:停机问题只是NP-hard问题,而不是NP-complete问题。
但是,为什么它不是NP-complete问题呢?我的意思是,一个问题应该具有什么性质才能够被认定为“NP-hard但不是NP-complete问题”?
我对NP-hard问题感到困惑。
一些NP-hard问题属于NP类,被称为NP-Complete问题,而另一些则不属于NP类。
例如:停机问题只是NP-hard问题,而不是NP-complete问题。
但是,为什么它不是NP-complete问题呢?我的意思是,一个问题应该具有什么性质才能够被认定为“NP-hard但不是NP-complete问题”?
NP问题的定义在于你可以在多项式时间内验证一个NP问题的解决方案。因此,如果一个问题是NP-hard,但不是NP-complete,你就无法在理论上及时验证该问题的解决方案。如果你看看停机问题,这是有意义的。解决方案只能是“是”或“否”,你只能通过再次解决原始问题来验证它,这意味着它不在NP中。
NP-hard 简单来说就是“至少和 NP 问题一样难”。NP-complete 意味着“在 NP 中,所有 NP-complete 问题都可以被归约到这个问题上,而这个问题也可以被归约到所有 NP-complete 问题上”。
维基百科文章 可能是一个很好的起点,因为它特别讨论了停机问题作为其中的一个例子。
简短回答:唯一不是NP完全问题的NP难问题是那些不属于NP的问题。
详细回答:
为什么呢?让我们仔细看一下NP完全和NP难的定义:
如果一个问题X是NP完全问题,则:
它在NP中
NP中的每个问题都可以在多项式时间内归约到X。
如果一个问题X满足(2)((1)不是必要条件),则它是NP难问题。
从这些定义中,很明显可以得出结论:唯一不是NP完全但是NP难的问题是那些不属于NP的问题。
例如,所有不是决策问题的NP难问题都不是NP完全问题(因为NP的定义是由决策问题组成的)。特别地,旅行商问题的搜索版本:给定城市列表及其两两之间的距离,任务是找到访问每个城市恰好一次并返回原始城市的最短路径。
旅行商问题的搜索版本已被证明是NP难题,但由于它不是决策问题(您无法通过回答是或否的问题来解决它),因此它不属于NP范畴,因此也不能成为NP完全问题。
停机问题是一个决策问题,但无法在多项式时间内进行验证(这是定义中使问题成为NP的第二个要求),因此它不能成为NP完全问题。