算法和计算复杂度 14 SAT Problem
Boolean satisfiability is prototypical -complete problem.
There is no algorithm deciding in worst case in polynomial time unless .
We always assume that .
For problem, SOTA algorithm uses time .
For special case of , there are faster algorithms, but all take time for some constant .
Schöning’s kSAT Algorithm
该算法在上学期随机算法课最后一节课 马尔可夫链和随机游走 中讲过,故此处略过。
分析过程很恶心。
The Sparsification Lemma
🎯Lemma 22. For all and integers , there exists a constant and an algorithm that given as input a in variables runs in time , where , and give as output a list of formulas each with at most clauses such that
for all .
Reduce to Hitting Set Problem
Recall problem. Consider a universe of elements and a collection of subsets of . We say that is a hitting set for if for all . We denote by the collection of all hitting sets of .
problem:
- Instance: Collection of subsets of a universe .
- Output: Hitting set for minimizing .
We denote by the restriction to collections of subsets of size at most .
We can transform into problem:
- is the subsets of corresponding to the clauses of .
- An assignment to the variables of can be viewed as a subset of .
- is the collection of the sets for . Note that assignments to the variables of are in one-to-one correspondence to hitting sets of .
- Defining
Observation: There is a one-to-one correspondence between the set of satisfying assignments of and hitting sets of of size .
Any collection of subsets over can be viewed as a CNF formula by letting each subset define a clause.
📖Definition 57. Let and be collections of subsets. We say that is a restriction of if for every there exists s.t. .
也就是集合的集合 中的每一个元素(是一个集合)是集合的集合 中对应有一个元素(是一个集合)的子集。
很绕,不是吗?
Clearly, if is a restriction of , then . Any satisfying assignment of CNF formula given by is also a satisfying assignment of the CNF formula given by .
🤔Lemma 23 (Hitting set correspondence). For all and integers , there exists a constant and an algorithm that given as input collection of subsets of size at most of a universe of size runs in time , where , and give as output a list of restrictions each with at most subsets of which are all of size at most s.t.
We call a subset of of size : -set.
The algorithm is a branching algorithm where each leaf of the recursion tree will give a restriction of .
To branch, the algorithm looks for a large collection of subsets of the same size that has a non-empty intersection, and branches on whether or not the common intersection will be hit by the hitting set. We define such collections of sets as flowers.
📖Definition 58. Let be -sets.
- We say that these sets are a flower if .
- We call the heart of the flower and sets the petals.
- Note that all petals have the same size , which we denote as petal-size.
定义一朵花:一组大小为 的集合,它们的交集为空。
花心:这组集合的交集。对应定义花心的大小。
花瓣:每个集合去除花心。对应定义花瓣的大小。
The algorithm will be controlled by integer parameters . We make increase rapidly as a parameter of .
📖Definition 59. Let be a flower of -sets and petal-size .
- The flower is large if .
- The flower is good if
- it is a large flower chosen s.t. is chosen minimally
- and if more than one large flower of -sets exists then chosen s.t. is chosen minimally.
如果一朵花含有集合的个数足够大,则称这朵花是“大”的。
如果一朵花是“大”的,并且其中包含的集合大小、花瓣大小都是最小的,则称这朵花是“好”的。
很形象的定义,但还是很绕
The algorithm will eliminate sets of a collection that contain other sets of the collection. If are such that , we say that is eliminated by .
Let denote the collection of minimal sets of , i.e., the sets of that are not eliminated by sets of .
Pseudo code of Reduce Algorithm
Reduce
Input: Collection of subsets of size at most of a universe .
Output: Restrictions of s.t. .
- .
- If has no large flower, return
- Pick good flower with heart .
- return
Reduce
Reduce
.
Correctness of Reduce
🤔Lemma 24. If Reduce
then .
Each is a restriction of . Thus .
Note that for any collection . It follows that eliminating sets from does not eliminate any hitting sets of .
Suppose that is a hitting set of and let be a flower of with heart . If , then is a hitting set of . If then must be a hitting set of . Thus any hitting set of is preserved in at least one recursive branch.
It’s easy to see that Reduce
always terminates.
It remains to establish qualitative properties of Reduce
: Every restriction output by Reduce
is sparse, i.e., contains at most sets, for a constant .
🤔Lemma 25. Let . Every restriction output by Reduce
contains at most many -sets, and therefore at most sets in total.
Prove by contradiction. Use pigeonhole principle.
The number of restriction output by Reduce
should be bounded by the number of leaves in the recursion tree.
🤔Lemma 26. Let be integers. It holds that
🤔Corollary 14. A binary tree of depth in which every root-to-leaf path follows the right child at most times has at most leafs.
Proof by Lemma 26.
When we have , thus we use the simpler upper bound on the number of leaves.
🤔Lemma 27. If Reduce
recursively calls Reduce
by adding an -set to , then holds. Furthermore in all recursive calls Reduce
that follows, the invariant holds.
没咋看懂这个引理
🤔Lemma 28. Any set can eliminate at most of the added -sets.
🤔Lemma 29. Let and suppose is s.t. at most sets of size at most that are added along a given path of the recursion tree of Reduce
. Then the number of -sets added along that path is at most .
🤔Corollary 15. At most sets of size at most are added along any path of the recursion tree of Reduce
, for all .
🤔Lemma 30. Along any path of the recursion tree of Reduce
at most families are created by adding petals of size for every .
We set in such a way that the ratio is equal to an integer constant , to be fixed later, for . Thus
🤔Corollary 16. Along any path of the recursion tree of Reduce
at most families are created by adding petals.
让我缓缓
The Exponential Time Hypothesis
A stronger hypothesis than : Exponential time is required to decide .
Exponential time hypothesis (aka ETH): requires worst-case linear exponential time, for all .
A strengthening of this hypothesis, strong exponential time hypothesis: it is not possible to save an exponential factor for a fixed independent of
📖Definition 60. Define . The ETH is the statement that , and SETH is the statement that .
🤔Proposition 20. For any and integer there is s.t. if there is an algorithm for solving in time there is an algorithm for running in time .
Input: on variables. the algorithm first invokes the algorithm of the Lemma 22 to compute formulas in time , where , and each has hat most clauses.
is satisfiable iff at least one of the formula are satisfiable.
may apply the standard reduction from to , obtaining formula , each having at most variables.
Using algorithm each can be checked for satisfiability in time . This together means that solves in time as claimed.
🤔Corollary 17. The following holds:
- ETH is equivalent to .
- SETH implies ETH.
🤔Proposition 21. ETH is equivalent to the existence of s.t. no algorithm can solve in time , where is the number of variables and the number of clauses.
Consider the independent set problem:
- Instance: Graph , integer .
- Question: Does have an independent set of size at least ?
🎯Theorem 60. If ETH holds, then there exists s.t. no algorithm can solve the independent set problem in time , where is the number of vertices of the given graph .
Standard reduction from to independent set problem.