gpt4 book ai didi

logic - SAT 的特殊情况和相应的#SAT 复杂度最高为 O(n^2) 并且具有用于生成实例的有效算法?

转载 作者:行者123 更新时间:2023-12-04 06:14:51 25 4
gpt4 key购买 nike

我有兴趣了解已知为多项式(或更现实地说,O(N^2))的 bool 可满足性问题的特殊情况。这些案例还应该有有效的算法来实际生成所有令人满意的实例,其中高效我的意思是需要 O(N #SAT) 来生成所有实例的序列。第二个条件可能暗示第一个条件,但我不清楚。

小例子:1SAT :)

简单的例子:2SAT 带有子句的“链”,因此将变量与子句连接起来的图是一条线。

有更多的地方吗?谢谢。

最佳答案

来自 The Complexity of Satisfiability Problems谢弗:

We show that (assuming P != NP) SAT(S) is polynomial-time decidable only if at least one of the following conditions holds:

(a) Every relation in S is satisfied when all variables are 0.

(b) Every relation in S is satisfied when all variables are 1.

(c) Every relation in S is definable by a CNF formula in which each conjunct has at most one negated variable.

(d) Every relation in S is definable by a CNF formula in which each conjunct has at most one unnegated variable.

(e) Every relation in S is definable by a CNF formula having at most 2 literals in each conjunct.

(f) Every relation in S is the set of solutions of a system of linear equation over the two-element field {0,1}.


前两个是可解的 O(1),接下来的三个 O(n) 和最后一个 O(n^3)(我认为)。因此,您想要的 SAT 实例位于前五个类之一。

关于logic - SAT 的特殊情况和相应的#SAT 复杂度最高为 O(n^2) 并且具有用于生成实例的有效算法?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/7382571/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com