CS21 Decidability and Tractability
Lecture 18
February 14, 2024
Time Hierarchy Theorem Theorem: for every proper complexity
Copyright By PowCoder代写 加微信 powcoder
function f(n) ≥ n:
TIME(f(n)) ⊆ TIME(f(2n)3).
• Note: P ⊆TIME(2n) ⊆ TIME(2(2n)3) ⊆ EXP
• Most natural functions (and 2n in particular) are proper complexity functions. We will ignore this detail in this class.
February 14, 2024 CS21 Lecture 18
Time Hierarchy Theorem Theorem: for every proper complexity
function f(n) ≥ n:
TIME(f(n)) ⊆ TIME(f(2n)3).
• Proof idea:
– use diagonalization to construct a language that is not in TIME(f(n)).
– constructed language comes with a TM that decides it and runs in time f(2n)3.
February 14, 2024 CS21 Lecture 18
Recall proof for Halting Problem
Turing Machines
H’: n Y n Y Y n Y
February 14, 2024 CS21 Lecture 18
box (M, x): does M halt on x?
The existence of H which tells us yes/no for each box allows us to construct a TM H’ that cannot be in the table.
Proof of Time Hierarchy Theorem
Turing Machines
February 14, 2024 CS21 Lecture 18
box (M, x): does M
accept x in time f(n)?
• TM SIM tells us yes/no for each box in time g(n)
• rows include all of TIME(f(n))
• construct TM D running in time g(2n) that is not in table
Proof of Time Hierarchy Theorem
– SIM is TM deciding language
{
– Claim: SIM runs in time g(n) = f(n)3. – define new TM D: on input
• if SIM accepts
• if SIM rejects
February 14, 2024 CS21 Lecture 18
Proof of Time Hierarchy Theorem
• Proof (continued):
– suppose M in TIME(f(n)) decides L(D)
• M(
• but M(
February 14, 2024 CS21 Lecture 18
Proof of Time Hierarchy Theorem
• Claim: there is a TM SIM that decides
{
and runs in time g(n) = f(n)3.
• Proof sketch: SIM has 4 work tapes
• contents and “virtual head” positions for M’s tapes
• M’s transition function and state
• f(|x|) “+”s used as a clock
• scratch space
February 14, 2024 CS21 Lecture 18
Proof of Time Hierarchy Theorem
• Proofsketch(continued):4worktapes
• contents and “virtual head” positions for M’s tapes • M’s transition function and state
• f(|x|) “+”s used as a clock
• scratch space
– initialize tapes
– simulate step of M, advance head on tape 3; repeat.
– can check running time is as claimed. February 14, 2024 CS21 Lecture 18
• We have defined the complexity classes P (polynomial time), EXP (exponential time)
some language
decidable languages
regular languages
context free languages
February 14, 2024
CS21 Lecture 18
Poly-time reductions
• Type of reduction we will use:
– “many-one” poly-time reduction (commonly) – “mapping” poly-time reduction (book)
February 14, 2024
reduction from f no language A to
CS21 Lecture 18
language B
Poly-time reductions
A yes f yes B no f no
• function f should be poly-time computable
Definition: f : Σ*→ Σ* is poly-time computable if for some g(n) = nO(1) there exists a g(n)-time TM Mf such that on
every w ∈ Σ*, Mf halts with f(w) on its tape. February 14, 2024 CS21 Lecture 18
Poly-time reductions
Definition: A ≤P B (“A reduces to B”) if there is a poly-time computable function f such that for all w
w ∈ A ⇔ f(w) ∈ B
• as before, condition equivalent to:
– YES maps to YES and NO maps to NO • as before, meaning is:
– B is at least as “hard” (or expressive) as A February 14, 2024 CS21 Lecture 18
Poly-time reductions Theorem: if A ≤P B and B ∈ P then A ∈ P.
– a poly-time algorithm for deciding A:
– on input w, compute f(w) in poly-time.
– run poly-time algorithm to decide if f(w) ∈ B – if it says “yes”, output “yes”
– if it says “no”, output “no”
February 14, 2024 CS21 Lecture 18
• 2SAT={CNFformulaswith2literalsperclause for which there exists a satisfying truth assignment}
• L={directedgraphG,andlistofpairsofvertices (u1, v1), (u2, v2),…, (uk, vk), such that there is no i for which [ui is reachable from vi in G and vi is reachable from ui in G]}
• Wegaveapoly-timereductionfrom2SATtoL.
• determinedthat2SAT∈PfromfactthatL∈P
February 14, 2024 CS21 Lecture 18
Hardness and completeness
• Reasonable that can efficiently transform one problem into another.
• Surprising:
– can often find a special language L so that every language in a given complexity class reduces to L!
– powerful tool
February 14, 2024 CS21 Lecture 18
Hardness and completeness
– a language L is a set of strings
– a complexity class C is a set of languages
Definition: a language L is C-hard if for every language A ∈ C, A poly-time reduces to L; i.e., A ≤P L.
meaning: L is at least as “hard” as anything in C
February 14, 2024 CS21 Lecture 18
Hardness and completeness
– a language L is a set of strings
– a complexity class C is a set of languages
Definition: a language L is C-complete if L is C-hard and L ∈ C
meaning: L is a “hardest” problem in C
February 14, 2024 CS21 Lecture 18
An EXP-complete problem • Version of ATM with a time bound:
ATMB = {
Theorem: ATMB is EXP-complete. Proof:
– what do we need to show? February 14, 2024 CS21 Lecture 18
An EXP-complete problem
• ATMB={
• Proof that ATMB is EXP-complete: – Part 1. Need to show ATMB ∈ EXP.
• simulate M on x for m steps; accept if simulation accepts; reject if simulation doesn’t accept.
• running time mO(1).
• n = length of input ≥ log2m
• running time ≤ mk = 2(log m)k ≤ 2(kn)
February 14, 2024 CS21 Lecture 18
An EXP-complete problem
• ATMB={
• Proof that ATMB is EXP-complete:
– Part 2. For each language A ∈ EXP, need to
give poly-time reduction from A to ATMB.
– for a given language A ∈ EXP, we know there is a TM MA that decides A in time g(n) ≤ 2nk for some k.
– what should reduction f(w) produce? February 14, 2024 CS21 Lecture 18
An EXP-complete problem
• ATMB={
• Proof that ATMB is EXP-complete: – f(w) =
– is f(w) poly-time computable?
• hardcode MA and k…
– YES maps to YES?
• w∈A ⇒
• w∉A ⇒
An EXP-complete problem
• A C-complete problem is a surrogate for the entire class C.
• For example: if you can find a poly-time algorithm for ATMB then there is automatically a poly-time algorithm for every problem in EXP (i.e., EXP = P).
• Can you find a poly-time alg for ATMB?
February 14, 2024 CS21 Lecture 18
An EXP-complete problem
• Can you find a poly-time alg for ATMB?
• NO! we showed that P ⊆ EXP.
• ATMB is not tractable (intractable).
decidable languages
regular languages
context free languages
February 14, 2024
CS21 Lecture 18
Back to 3SAT
• Remember 3SAT ∈ EXP
3SAT = {formulas in CNF with 3 literals
per clause for which there exists a satisfying truth assignment}
• It seems hard. Can we show it is intractable?
– formally, can we show 3SAT is EXP- complete?
February 14, 2024 CS21 Lecture 18
Back to 3SAT
• can we show 3SAT is EXP-complete?
• Don’t know how to. Believed unlikely.
• One reason: there is an important positive
feature of 3SAT that doesn’t seem to hold for problems in EXP (e.g. ATMB):
February 14, 2024 CS21 Lecture 18
3SAT is decidable in polynomial time by a nondeterministic TM
Nondeterministic TMs
• Recall: nondeterministic TM
• informally, TM with several possible next
configurations at each step • formally, A NTM is a 7-tuple
(Q, Σ, Γ, δ, q0, qaccept, qreject) where:
– everything is the same as a TM except the transition function:
δ:Q x Γ→ P(Q x Γ x {L, R}) February 14, 2024 CS21 Lecture 18
Nondeterministic TMs visualize computation of a NTM M as a tree
February 14, 2024
• nodes are configurations
• leaves are accept/reject configurations
• M accepts if and only if there exists an accept leaf
• M is a decider, so no paths go on forever
• running time is max. path length CS21 Lecture 18
The class NP
Definition: TIME(t(n)) = {L : there exists a TM M that decides L in time O(t(n))}
P = ∪k ≥ 1 TIME(nk) Definition: NTIME(t(n)) = {L : there exists a
NTM M that decides L in time O(t(n))} NP = ∪k ≥ 1 NTIME(nk)
February 14, 2024 CS21 Lecture 18
NP in relation to P and EXP
regular languages
context free languages
decidable languages
• P ⊆ NP (poly-time TM is a poly-time NTM)
– configuration tree of nk-time NTM has ≤ bnk nodes – can traverse entire tree in O(bnk) time
we do not know if either inclusion is proper
February 14, 2024 CS21 Lecture 18
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com