算法5
Log Time <= Nlog Time <= P Time <= NP Time <= P Space == NP Space <= Exp Time <= NExpTime <= ExpSpace < NExpSpace <= 2ExpTime
- if ϕ1 and ϕ2 are formulas, then so are
(¬ϕ1), (ϕ1 ∨ ϕ2), (ϕ1 ∧ ϕ2), (ϕ1 → ϕ2)
lecture_2
SAT & k-SAT
SAT
Given: a set of clauses Γ;
Return: Yes if Γ is satisfiable, and No otherwise.
k-SAT
Given: a set of clauses Γ, each with at most k literals;
Return: Yes if Γ is satisfiable, and No otherwise.
formula
proposition letters(variables): p&q 的p和q
connectives: &, v, ->, and <->.
leteral: p or ¬p (p is proposition letter)
opposite leteral : l 上面一个横杠
clause: A clause is an expression l1 v l2 v· · · ∨ k , where the li are
literals. ep: p1 ∨ ¬p2 ∨ p3
P = {p1, p2, . . .}
• every element of P is a formula
• if ϕ1 and ϕ2 are formulas, then so are
(¬ϕ1), (ϕ1 ∨ ϕ2), (ϕ1 ∧ ϕ2), (ϕ1 → ϕ2)
assignment
• An assignment is a function θ : P → {T, F}.
• we extend θ to formulas by setting
θ(¬ϕ1) = T iff ϕ1 = F
satisfiable
• A formula ϕ is satisfiable if there exists an assignment θ such
that θ(ϕ) = T.
- set of clauses : there exists an assignment θ such that θ(γ) = T for all γ ∈ Γ.
PROPOSITIONAL SAT
NP time
Given: a propositional logic formula ϕ;
Return: Yes if ϕ is satisfiable, and No otherwise.
SAT
Integer Linear Programming
Cramer’s rule
Ax = b with det(A) != empty
xi = det(Ai) / det(A)
Ai is the result of replacing the ith column of A by b
｜det(A)｜ <= $2^nM^n$
no matter how many veribles（non-zero value） -> still small.
LP-feasibility is NPTIME 并 co-NPTIME
P-feasibility is P-TIME
$Ax = b x>=b$
$x^T (A^Ty) = b^T y$
$（>=0 >=0 <0)$ 为什么这里第一个0没有下划线