基于下面的链接,我知道在多项式时间内解决可满足性(NP完全)意味着可以在多项式时间内解决任何其他NP问题。但是Vice-Versa是真的吗?
此外,如果存在任何其他NP-Complete问题的多项式,这意味着所有其他NP-Complete都可以在多项式时间内求解吗?
What are the differences between NP, NP-Complete and NP-Hard?
NP-complete中的'complete'表示,如果问题在NP-complete中,则该问题的解决方案将通过多项式转换处理来解决NP中的任何问题。
用外行的话来说,如果您在多项式时间内解决了单个NP完全问题,则证明NP = P。
解决SAT不能解决所有NP问题。它解决了所有可以通过P复杂度算法简化为SAT的NP问题。存在不降低SAT的P复杂度的问题。通过NP的减少,有些可以还原为SAT。通过NP归约的一些归约算法,其归约算法将P复杂度降低至SAT。]
SAT具有P复杂度解决方案。参见arxiv.org/abs/cs/0205064。