SAT and max-sat 151242002 Qi-Zhi Cai.

Presentation on theme: "SAT and max-sat 151242002 Qi-Zhi Cai."— Presentation transcript:

1 SAT and max-sat Qi-Zhi Cai

2 Preparation P：多项式时间可解 NP：不确定多项式时间能不能解 NP=VP，多项式时间可验证 显然𝑃⊂𝑁𝑃
归约：存在算法C，能够将问题A的实例a转换到问题B的实例b,且 a与b的答案一致，当C是多项式复杂度的时候，叫做多项式归约， 简便起见，以下归约都叫多项式归约 NPC：首先 NPC是NP的，其次，NP中的任何问题都能归约到 NPC,也就是所谓的“NPC⊂𝑁𝑃,且NPC与NP中的任何问题一样 难。”

3 Decition Problem Use SAT as a example

4 Background 2-CNF可满足性：P问题， Krom, Melven R. (1967), "The Decision Problem for a Class of First-Order Formulas in Which all Disjunctions are Binary", Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, 13: 15–20, doi: /malq K-CNF可满足性？ 事实上，3-CNF可满足性是NPC的

5 SAT Problem 对于一个确定的逻辑电路，是否存在一种输入使得输出为真。

6 History 历史上第一个被证明是NPC问题的问题，那个时候还没有NPC的定义
 Any problem in NP can be reduced in polynomial time by a deterministic Turing machine to the problem of determining whether a Boolean formula is satisfiable. Cook, Stephen (1971). "The complexity of theorem proving procedures". Proceedings of the Third Annual ACM Symposium on Theory of Computing. pp. 151–158.

7 NPC NP是平凡的（VP），NPC的证明是很复杂的。因为这是历史 上第一个NPC问题，我们没有办法去证明已知的某个NPC问 题可以归约到它。因此这个证明是非平凡的，CLRS 34.3使用 非决定性图灵机构造性的证明了这个问题

8 NPC examples Boolean satisfiability problem (SAT) Knapsack problem
Hamiltonian path problem Travelling salesman problem (decision version) Subgraph isomorphism problem Subset sum problem Clique problem Vertex cover problem Independent set problem Dominating set problem Graph coloring problem More on

9 Solve--Randomized Algorithm
WalkSAT，GSAT：随机化一组赋值，如果验证为ture就停止，否则翻 转某个值，选择哪个值构成了两个算法的不同。 Conflict-Driven Clause Learning：DP寻找某个引起冲突的clause并 将其整体翻转 DPLL algorithm：启发式搜索

10 Use Max-SAT as a example
Optimization problem Use Max-SAT as a example

11 From NPC to NP-Hard NP—decision Problem
存在一个可行解->给出一个最优解—Optimization Problem NP-hard：比NP更加难，严谨的说，至少不会更简单 所有NP皆可归约至NP-hard，但是NP-hard不必要是NP的， 如果是，那么同时它也是NPC的

12 Max-SAT Problem 给出一个赋值，使m个clause为真的个数最多

13 Hardness 看上去远远比SAT难得多，它有一个特例，当这个问题可以被SAT判定为真时，答案是 m
实际上求解这个问题比想象的还要难，只有暴力搜索一种方法 Why？ APX-complete： It does not admit a polynomial-time approximation scheme unless P = NP 搜索策略： 分支限界—BFS 加深迭代—DFS

14 Beyond NP-Hard

15 Harder problem #P is the class of function problems of the form "compute ƒ(x)", where ƒ is the number of accepting paths of a nondeterministic Turing machine running in polynomial time Partial P

16 Harder problem NE: Nondeterministic E
Nondeterministic exponential time with linear exponent (i.e. NTIME(2O(n))). PNE = NPNE   L. Hemachandra. The strong exponential hierarchy collapses, Journal of Computer and System Sciences 39(3): , 1989. NEXP: Nondeterministic EXP Nondeterministic exponential time (i.e. NTIME(2p(n)) for p a polynomial). Does not equal EXP if and only if there is a sparse set in NP that is not in P.

17 Harder problem NTIME(f(n)): Nondeterministic f(n)-Time
Same as NP, but with f(n)-time (for some constructible function f) rather than polynomial-time machines. The Nondeterministic Time Hierarchy Theorem: If f and g are time-constructible and f(n+1)=o(g), then NTIME(f(n)) does not equal NTIME(g(n)) [SFM78] (this is actually stronger than the hierarchy theorem for DTIME). NTIME(n) strictly contains DTIME(n) [PPS+83] (this result does not work for arbitrary f(n)). For any constructible superpolynomial f, NTIME(f(n)) with NP oracle is not in P/poly [Kan82].

18 一些实际的Harder Problem Machine Learning，Artificial Intelligence：iid & Probably Approximately Correct If not? 1、not iid? 2、PAC can not guarantee 𝐸 𝑖𝑛 ≈ 𝐸 𝑜𝑢𝑡 ?

19 How to solve Discrete Optimization problem
Mathematica,Matlab Pyomo: Python-based, open-source optimization modeling language 约束求解器： 每种问题有自己的solver 也有集成的比如MiniZinc