背包问题是伪多项式时间，因为其优化函数依赖于背包的大小，而且加法本身耗时也不能视作多项式内，而是指数时间。实际上，可以通过将二进制加法转换为逻辑判断，将01背包规约到3sat问题，这是一个np完全问题