Complexity

a decision problem ⊓ belongs to complexity class ℙ if there is a deterministic polynomial time algorithm that solves ⊓

a pair (D⊓, Y⊓) where - D⊓ is the domain of ⊓, the set of all possible instances - Y⊓ is the set of all yes-instances - N⊓ = D⊓\Y⊓ is the set of all no-instances

a decision problem ⊓ belongs to the complexity class ℕℙ if a nondeterministic polynomial time algorithm exists that solves ⊓

On instance I ∈ D⊓ it works as follows: 1. Nondeterministic (“guessing”) stage - for a given instance I, a certificate c is “guessed” 2. Deterministic (“checking” or “verification”) stage - a deterministic algorithm takes both I and c as input, decides or does not terminate

ℙ ⊆ ℕℙ

ℙ ≠ ℕℙ

ℙ and ℕℙ are closed under union and intersection, that is - for all problems ⊓ and Ψ in ℙ the problems ⊓ ∪ Ψ and ⊓ ∩ Ψ are in ℙ as well - for all problems ⊓ and Ψ in ℕℙ the problems ⊓ ∪ Ψ and ⊓ ∪ Ψ are in ℕℙ as well

ℙ is closed under complement, that is, for all problems ⊓ ∈ ℙ the problem ⊓ ∈ ℙ the problem ‘⊓ belongs to the class ℙ too

A polynomial transformation from ⊓ to Ψ is a function f: D⊓ → DΨ such that - f is computable by deterministic polynomial time algorithm - for every I ∈ D⊓ we have I ∈ Y⊓ if and only if f(I) ∈ YΨ

A problem Ψ is ℕℙ-complete of 1. (membership in ℕℙ) Ψ ∈ ℕℙ 2. (ℕℙ-hardness) for all ⊓ ∈ ℕℙ, ⊓ ⩽pm Ψ

the classes ℙ and ℕℙ are closed under ⩽pm, that is 1. if Ψ ∈ ℙ and ⊓ ⩽pm Ψ then ⊓ ∈ ℙ 2. if Ψ ∈ ℕℙ and ⊓ ⩽pm Ψ then ⊓ ∈ ℕℙ

lemma 1. the relation ⩽pm is reflexive and transitive 2. for all decision problems ⊓ and Ψ, ⊓ ⩽pm if and only if ‘⊓ ⩽ pm ‘Ψ lemma for all problems Ψ with YΨ ≠ ∅ and YΨ ≠ DΨ we have if ⊓ ∈ ℙ then ⊓ ⩽pm Ψ

let ⊓ and Ψ be two ℕℙ-complete problems 1. ⊓ ⩽pm Ψ 2. ⊓ ∈ ℙ if and only if ℙ = ℕℙ 3. for all decision problems Φ ∈ ℕℙ, if Ψ ⩽pm Φ then Φ is ℕℙ-complete

To prove that Φ is ℕℙ-complete: 1. Show Φ ∈ ℕℙ 2. Select a known ℕℙ-complete problem Ψ to reduce rom, i.e. for which you can show Ψ ⩽pm Φ in steps 3-7 3. Construct a reduction function f that enables you to complete the following steps 4-7 4. Show that f(I) is defined for all instances of Ψ 5. Show that f can be computed in polynomial time 6. Prove for all I ∈ DΨ: if I ∈ YΨ then f(I) ∈ YΦ 7. Prove for all I ∈ DΨ: if f(I) ∈ YΦ then I ∈ YΨ

asks whether a boolean formula in CNF is satisfiable

Let X = {x1, x2, . . . , xn} be a set of boolean variables. - A truth assignment for X is a function a : X → {0, 1}, where 0 is “false” and 1 is “true”. - A literal ℓ is either a variable x ∈ X or its negation x. We extend a by a(x) = 1 − a(x). - A clause is the disjunction of literals. For c = (Vk i=1 ℓi ) we set a(c) = maximum{a(ℓi ) | 1 ≤ i ≤ k}. - A formula in CNF is the conjunction of clauses. For φ = ∧ m j=1 cj we set a(φ) = minimum{a(cj ) | 1 ≤ j ≤ m}. - The formula φ is satisfiable if an assignment a exists such that a(φ) = 1

ℕℙ

ℕℙ

ℕℙ-complete