如果NP在多项式时间内求解,可满足性可以在多项式时间内求解

问题描述 投票:1回答:2

基于下面的链接,我知道在多项式时间内解决可满足性(NP完全)意味着可以在多项式时间内解决任何其他NP问题。但是Vice-Versa是真的吗?

此外,如果存在任何其他NP-Complete问题的多项式,这意味着所有其他NP-Complete都可以在多项式时间内求解吗?

What are the differences between NP, NP-Complete and NP-Hard?

algorithm complexity-theory theory
2个回答
2
投票

NP-complete中的'complete'表示,如果问题在NP-complete中,则该问题的解决方案将通过多项式转换处理来解决NP中的任何问题。

用外行的话来说,如果您在多项式时间内解决了单个NP完全问题,则证明NP = P。


0
投票

解决SAT不能解决所有NP问题。它解决了所有可以通过P复杂度算法简化为SAT的NP问题。存在不降低SAT的P复杂度的问题。通过NP的减少,有些可以还原为SAT。通过NP归约的一些归约算法,其归约算法将P复杂度降低至SAT。]

SAT具有P复杂度解决方案。参见arxiv.org/abs/cs/0205064。

© www.soinside.com 2019 - 2024. All rights reserved.