COMP3630/6360: Theory of Computation Semester 1, 2022
The Australian National University
Time Complexity
Copyright By PowCoder代写 加微信 powcoder
This lecture covers Chapter 10 of HMU: Time Complexity
NP-Hardness Polytime Reductions SAT is NP-hard
Additional Reading: Chapter 10 of HMU.
Question 1.1 (P = NP problem)
Can we simulate a non-deterministic TM (NTM) in polynomial time on a (deterministic)
P—problems that can be solved in polynomial time on a TM. NP—problems that can be solved in polynomial time on an NTM.
At this point, no one knows for sure, but “no” might be a good bet.
NP-complete problems
This is about decision problems (problems with yes/no answers). Equivalently, solving the membership problem x ∈ L.
Obviously P ⊆ NP.
Nobody knows for sure whether NP ⊆ P
Intuitively, NP-complete problems are the “hardest” problems in NP.
P Reducibility
Recall how we use mapping-reducibility to transfer (un)decidabilty from one problem to the next.
Definition 1.2
f : Σ∗ −→ Σ∗ is a polynomial time computable (or P computable) function if some polynomial time TM M exists that halts with just f(w) on its tape, when started on any input w ∈ Σ∗.
Definition 1.3
A ⊆ Σ∗1 is polynomial time mapping reducible (or P reducible) to B ⊆ Σ∗2 , written
A ≤P B, if a P computable function f : Σ∗1 −→ Σ∗2 exists that is also a reduction (from A to B).
P Reducibility cont.
Theorem 1.4
IfA≤P BandB∈PthenA∈P.
Todecidew∈Afirstcomputef(w)(inP)wheref isthePreductionfromAtoB,and then run a P decider for B. This is still in P because p1(p2(n)) is a polynomial if p1(n) and p2(n) are.
NP-Completeness
Definition 1.5
A language B is NP-complete if
2 every A ∈ NP is P reducible to B.
Theorem 1.6
If B is NP-complete and B ∈ P then P = NP. Theorem 1.7
If B is NP-complete and B ≤P C for C ∈ NP, then C is NP-complete.
Polynomial time reductions compose.
NP-Completeness
If there are any problems in NP \ P, the NP-complete problems are all there.
Every NP-complete problem can be translated in deterministic polynomial time to every
other NP-complete problem.
So, if there is a P solution to one NP-complete problem, there is a P solution to every NP problem.
NP-Hardness by Reduction
Typical method: Reduce a known NP-hard problem P1 to the new problem P2 .
Basic Proof Strategy
NP-completeness is a good news/bad news situation. Good news: The problem is in NP!
Bummer: The problem is NP-hard!
So, a typical NP-completeness proof consists of two parts:
1 Prove that the problem is in NP (i.e., it has P verifier).
2 Prove that the problem is at least as hard as other problems in NP.
A TM can simulate an ordinary computer in polynomial time, so it is sufficient to describe a polynomial-time checking algorithm that will run on any reasonable model of computation.
NP-Hardness
A problem is NP-hard if having a polynomial-time solution to it would give us a polynomial solution to every problem in NP.
Prove that the problem is NP-hard: The usual strategy is to find a polynomial-time reduction of a known NP-hard problem (say P1) to the problem in question (say P2).
The goal is to show that P2 is at least as hard (in terms of polynomial vs. super-polynomial time) as P1.
If P1 can be translated to an equivalent problem P2 in polynomial time, then a polynomial-time solution to P2 would also give a polynomial-time solution to P1: First reduce P1 to P2, then solve it.
NP-hardness cont.
Repeated warning: Make sure you are reducing the known problem to the unknown problem!
In practice, there are now thousands of known NP-complete problems. A good technique is to look for one similar to the one you are trying to prove NP-hard.
Boolean Formulae
Let Prop = {x , y , . . .} be a (finite) set of Boolean variables (or propositions). A CFG for Boolean formulae over Prop is:
φ → p | φ ∧ φ | ¬φ | (φ) p→x|y|…
We use abbreviations such as
φ1 ∨φ2 =¬(¬φ1 ∧¬φ2) φ1 ⇒φ2 =¬φ1 ∨φ2 false = (x ∧ ¬x) true = ¬false
Technically, we could handle countably infinite sets Prop if we had a naming scheme for variables, say, xn for binary representations n of natural numbers.
Semantics of Boolean Formulae
A Boolean formula is either TT (for “true”) or FF (for “false”), possibly depending on the interpretation of its propositions. Let B = {FF, TT}.
Definition 2.1
An interpretation (of Prop) is a function π : Prop −→ B.
For Boolean formulae φ we define π satisfies φ, written π |= φ, inductively by: Base: π |= x iff π(x) = TT.
Induction:
π |= ¬φ iff π ̸|= φ.
π|=φ1 ∧φ2 iffbothπ|=φ1 andπ|=φ2. π |= (φ) iff π |= φ.
φ is satisfiable if there exists an interpretation π such that π |= φ.
SAT—An NP-Complete Problem
Theorem 2.2
SAT = { ⟨φ⟩ | φ is a satisfiable Boolean formula }
SAT is NP-complete. Proof of SAT ∈ NP.
If π |= φ we use ⟨π⟩ as certicate. Had we chosen a countably infinite Prop, we’d restrict π to the propositions occurring in φ.
Proof of NP-Hardness of SAT
Let A ∈ NP. Let M = (Q,Σ,Γ,δ,q0,F) be a deciding NTM with L(M) = A and let p be a polynomial such that M takes at most p(|w|) steps on any computation for any
Construct a P reduction from A to SAT. On input w a Boolean formula φw that describes M’s possible computations on w.
M accepts w iff φw is satisfiable. The satisfying interpretation resolves the nondeterminism in the computation tree to arrive at an accepting branch of the computation tree.
Remains to be done: define φw .
Proof of NP-Hardness of SAT cont.
Recall that M accepts w if an n ≤ p(|w |) and a sequence (Ci )0CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com