Homework 15-1
=
###### tags: `Course - Algorithmics`
## Design
* 我們可以把2-CNF轉換成有向圖，其中頂點代表變數，而邊(A → B)代表當A成立時，B也必須成立。
* 舉例來說，(A or B) 可以轉換成 (¬A → B) 或是 (¬B → A)。
* 在轉換的時候可能會遇到以下三種情況：
* Case1：變數不同，如(A or B)，則建立 (¬A → B) 和 (¬B → A)
* Case2：變數相同，如(A or A)，即A必定成立，建立 (¬A → A)
* Case3：一正一反，如(¬A or A)，此敘述必成立，不用建立邊。
[上圖來源](https://www.iitg.ac.in/deepkesh/CS301/assignment-2/2sat.pdf)
* 轉換成有向圖後，如果存在從某個頂點A到另一個頂點B的路徑，就意味著也存在頂點¬B到頂點¬A的路徑，也意味著這條路徑上的頂點要嘛全部成立要嘛全部不成立。
* 所以我們可以得知，這個CNF不成立的條件為存在一個變數x且：
* 存在頂點x到頂點¬x的路徑
* 存在頂點¬x到頂點x的路徑
## Pseudo Code

1. Construct the graph G as described above and check whether given CNF is satisfiable.
2. If given CNF is not satisfiable, end the program.
3. Pick an unassigned literal x, with no path from x to ¬x, and assign it TRUE.
4. Assign TURE to all reachable vertices of x and assign FALSE to their negations.
5. Repeat 3, 4 and 5 until all the vertices are assigned.

## Analysis
假設CNF中有n個條件(包含negations)，在G中n = |V|, m = |E|
* 建立G可以在$\Theta(n)$完成
* 找出所以可能的路徑，做一次DFS再用parent去找，可以在$\Theta(n(n+m))$完成
* 每一條路徑都重複做3~5，可以在$\Theta(nm)$完成

因此2-CNF-SAT ∈ P