关于强NP完全性与Karp归约的相关技术疑问
关于强NP完全性与Karp归约的相关技术疑问
最近在学习伪多项式时间和强NP完全性的时候,看到这么一段结论:
- 子集和(SubsetSum)问题可以用伪多项式时间算法求解
- SAT问题哪怕用一元编码来表示输入,也不存在伪多项式时间算法,这说明SAT是强NP完全问题
基于这个结论,我有两个疑问:
- 3SAT是不是也属于强NP完全问题?
- 我知道SAT可以通过Karp归约(多项式时间归约)转化为3SAT,而3SAT又能Karp归约到子集和问题,那为什么不能把SAT直接归约到子集和,然后用子集和的伪多项式时间算法来求解,这样不就得到SAT的伪多项式时间算法了吗?这和之前说的SAT没有伪多项式时间算法矛盾啊。
ps:这些结论来自一段8分钟的讲解视频,视频里主要介绍了一元编码、伪多项式时间、强NP完全性这些基础概念。
备注:内容来源于stack exchange,提问作者poker resources
相关产品推荐
相关产品推荐

