证明NPC问题的通用策略

证明NPC问题的通用策略
给定一个基本的问题X,证明其是NPC的基本策略是:
(1)证明X是一个NP问题。
(2)选择一个已知的NPC问题Y。
(3)证明Y \leq_p X

0

Leave a Reply

Your email address will not be published.