另外，为什么qsat pspace是完全的，电路可满足性是np完全的？他们不是同一件事吗？
最佳答案
QSAT是与TQBF（真量布尔公式）有关的问题这些公式在一开始就有它们的变量如果公式的计算结果为true或false，则该公式是TQBF语言中的。如果它是pspace complete，那么语言就驻留在pspace中，而且它也是pspace的硬体。使用递归算法来确定公式的计算（取决于它是否有量词）将告诉您这些语句是否为真通过证明它是pspace hard，您可以证明该语言必须在多项式时间内可还原为tqbf。
CSAT问题是关于判断一个布尔电路是否有一组输入（根据输出）为真的决策问题证明了它在NP空间上是NP完全的，在多项式时间上是可约的。
在不考虑输出状态（真或假）的情况下，确定其空间分类的qsat求值和其归约时间，通过公式是否没有量词（从而返回公式）或检查第一个变量的两个可能值（如果它有量词）来确定递归算法的求解。此计算是针对求解它所需的内存空间量，特别是对数空间。csat是根据输出状态（在这种情况下是可解的）来评估的，因此不是由空间需求决定的，而是由总还原时间决定的。具体包含n个任意门，可以在O（2^0.4058n）中确定。
关于algorithm - 电路可满足性和q-sat有什么区别？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/54777354/