You need to enable JavaScript to run this app.
优惠活动
大模型
产品
解决方案
定价
更多

关于强NP完全性与Karp归约的相关技术疑问

关于强NP完全性与Karp归约的相关技术疑问

最近在学习伪多项式时间和强NP完全性的时候,看到这么一段结论:

  1. 子集和(SubsetSum)问题可以用伪多项式时间算法求解
  2. SAT问题哪怕用一元编码来表示输入,也不存在伪多项式时间算法,这说明SAT是强NP完全问题

基于这个结论,我有两个疑问:

    1. 3SAT是不是也属于强NP完全问题?
    1. 我知道SAT可以通过Karp归约(多项式时间归约)转化为3SAT,而3SAT又能Karp归约到子集和问题,那为什么不能把SAT直接归约到子集和,然后用子集和的伪多项式时间算法来求解,这样不就得到SAT的伪多项式时间算法了吗?这和之前说的SAT没有伪多项式时间算法矛盾啊。

ps:这些结论来自一段8分钟的讲解视频,视频里主要介绍了一元编码、伪多项式时间、强NP完全性这些基础概念。

备注:内容来源于stack exchange,提问作者poker resources

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.04.16 08:53:14