如果一个问题X(决策问题)已知是NP-完全的,并且被证明可以在多项式时间内归约到问题Y,那么你能说问题Y也是NP-完全的吗?
我的第一反应是不行,问题Y需要被证明它属于NP。但经过进一步思考,如果X被归约到了Y,那么Y已经被认为是NP-完全的了。现在我只是有些困惑...任何帮助都将不胜感激。
我的第一反应是不行,问题Y需要被证明它属于NP。但经过进一步思考,如果X被归约到了Y,那么Y已经被认为是NP-完全的了。现在我只是有些困惑...任何帮助都将不胜感激。
反证法:
如果 X ∈ NP 且 X ⇔ Y,而 Y ∉ NP,则 X ∉ NP。
问题X - 不确定
问题Y - 在NP中
为了证明X在NP中,你需要展示你可以按照步骤将X中的每个问题都归约到Y中的一个问题。这样你就知道X问题至少和等价的Y问题一样难。
所以,不,你需要从Y开始,然后归约到X。
还没有,你需要更多的步骤。
为了证明一个问题L是NP完全问题,我们需要完成以下步骤:
到目前为止,你已经完成了第2、3、4步。
你仍然需要展示缩减是多项式的(第5步),并且该问题属于NP(第1步),也就是说,可以在多项式时间内验证解决方案。
SAT问题可以在一次ALL调用中解决,但这并不意味着ALL属于NP。
是的,那是正确的。 你可以将你的问题在多项式时间内归约到任何已知的 NP 完全问题,不过这被认为是一项非常困难的任务。 所以,你可以选择一个已经是 NP 完全问题的问题,并将其归约到你的问题,同时还要证明它在 NP 中,然后你的问题就会成为 NP 完全。