证明:X3C问题属于NPC
证明:X3C问题属于NPC
发布时间：2025-05-09 00:14:46
请在 下方输入 要搜索的题目：
推荐参考答案 (
由 快搜搜题库 官方老师解答 )
答案：证明:容易验证X3C∈NP。∵猜测一个3元素子集C’,判定是否C’∈C,并且X中的元素出现在C’中一次且仅一次。这显然可在多项式时间内完成。下面将3DM实例多项式时间归约到X3C的相应实例。
