我需要证明加权反馈顶点集(WFVS)是NP完全的。我怎么做,我感到困惑。我不知道该怎么做。
谢谢! :)
有三个基本步骤来表明问题出现在NP中
这就是你如何知道你的问题在NP中。
NP完成
要表明问题是NP-Complete,您必须找到一个众所周知的NP-Complete问题,例如顶点覆盖或旅行商问题,并通过将已知问题转换为您的问题来证明您的问题与该问题一样困难问题,然后证明你的问题的'是'证书暗示对另一个问题的'是'证书,反之亦然。
这就是你如何表明你的问题是NP完整的。