CS21 Decidability and Tractability
Lecture 26 March 6, 2024
• Challenges to Extended Church-Turing – randomized computation
– quantum computation
Copyright By PowCoder代写 加微信 powcoder
• Course review
March 6, 2024 CS21 Lecture 26 2
Extended Church-Turing Thesis
• the belief that TMs formalize our intuitive notion of an efficient algorithm is:
• randomizedcomputationchallengesthisbelief March 6, 2024 CS21 Lecture 26 3
The “extended” Church-Turing Thesis
everything we can compute in time t(n) on a physical computer can be computed on a Turing Machine in time t(n)O(1) (polynomial slowdown)
RP,coRP, BPP
P ZPP coRP RPBPP PSPACE EXP
• from definitions: ZPP ⊆ RP, coRP ⊆ BPP
March 6, 2024 CS21 Lecture 26 4
Polynomial identity testing
• Given: polynomial p(x1, x2, …, xn) as arithmetic formula (fan-out 1):
-* *+- x2 x3 … xn
• multiplication (fan-in 2) • addition (fan-in 2)
• negation (fan-in 1)
variables take values in finite field F March 6, 2024 CS21 Lecture 26 5
Polynomial identity testing
• Question: Is p identically zero? – i.e., is p(x) = 0 for all x ∈ Fn
– (assume |F| larger than degree…)
• “polynomial identity testing” because given two polynomials p, q, we can check the identity p ≡ q by checking if (p – q) ≡ 0
March 6, 2024 CS21 Lecture 26 6
Polynomial identity testing
Lemma (Schwartz-Zippel): Let p(x1, x2, …, xn)
be a total degree d polynomial over a field F and let S be any subset of F. Then if p is not identically 0,
Prr1,r2,…,rn∈S[ p(r1, r2, …, rn) = 0] ≤ d/|S|.
March 6, 2024 CS21 Lecture 26 7
Polynomial identity testing • Given: polynomial p(x1, x2, …, xn) over
• Is p identically zero?
x2 x3 … xn
• Note: degree d is at most the size of input
March 6, 2024 CS21 Lecture 26 8
Polynomial identity testing
• randomized algorithm: pick a subset S ⊆ F of size 2d
– pick r1, r2, …, rn from S uniformly at random – if p(r1, r2, …, rn) = 0, answer “yes”
– if p(r1, r2, …, rn) ≠ 0, answer “no”
• if p identically zero, never wrong
• if not, Schwartz-Zippel ensures probability
of error at most 1⁄2
March 6, 2024 CS21 Lecture 26 9
Randomized complexity classes • We have shown:
– Polynomial Identity Testing is in coRP
– note: no sub-exponential time deterministic algorithm know
March 6, 2024 CS21 Lecture 26 10
Randomized complexity classes
• How powerful is randomized computation?
• We have seen an example of a problem in
that we only know how to solve deterministically in EXP.
March 6, 2024 CS21 Lecture 26 11
Is randomness a panacea for intractability?
Randomized complexity classes
P ZPP coRP RPBPP PSPACE EXP
•believedthatP=ZPP=RP=coRP=BPP (!) March 6, 2024 CS21 Lecture 26 12
Course Review
March 6, 2024 CS21 Lecture 26 13
• Highest level: 2 main points
1. Decidability
– problem solvable by an algorithm = problem is decidable
– some problems are not decidable (e.g. HALT)
March 6, 2024 CS21 Lecture 26 14
• Highest level: 2 main points
2. Tractability
– problem solvable in polynomial time = problem is tractable
– some problems are not tractable (EXP- complete problems)
– huge number of problems are likely not to be tractable (NP-complete problems)
March 6, 2024 CS21 Lecture 26 15
• Important ideas
– “problem” formalized as language
• language = set of strings
– “computation” formalized as simple machine
• finite automata
• pushdown automata • Turing Machine
– “power” of machine formalized as the set of languages it recognizes
March 6, 2024 CS21 Lecture 26 16
• Important ideas (continued):
– simulation used to show one model at least as powerful as another
– diagonalization used to show one model strictly more powerful than another
• also Pumping Lemma
– reduction used to compare one problem to
March 6, 2024 CS21 Lecture 26 17
• Important ideas (continued):
– complexity theory investigates the resources
required to solve problems • time, space, others…
– complexity class = set of languages
– language L is C-hard if every problem in C
reduces to L
– language L is C-complete if L is C-hard and L is in C.
March 6, 2024 CS21 Lecture 26 18
• Important ideas (continued):
A complete problem is a surrogate for the entire class.
March 6, 2024 CS21 Lecture 26 19
Summary Part I: automata
March 6, 2024 CS21 Lecture 26 20
(single) start state
0,1 alphabet Σ = {0,1}
(several) accept states transition for each symbol
Finite Automata
• read input one symbol at a time; follow arrows; accept if end in accept state
March 6, 2024 CS21 Lecture 26 21
Finite Automata
• Non-deterministic variant: NFA
• Regular expressions built up from:
– concatenations – star operations
Main results: same set of languages recognized by FA, NFA and regular expressions (“regular languages”).
March 6, 2024 CS21 Lecture 26 22
finite control
March 6, 2024
input tape
011001110100101
0 (infinite) 1
stack 1 0 :
New capabilities:
• can push symbol onto stack
• can pop symbol off of stack
CS21 Lecture 26 23
March 6, 2024
production
CS21 Lecture 26
Context-Free Grammars
start symbol
A → 0A1 A→B B→#
terminal symbols
non-terminal symbols
Main results: same set of languages recognized by NPDA, and context-free grammars (“context-free languages”).
• and DPDA’s weaker than NPDA’s…
March 6, 2024 CS21 Lecture 26 25
Non-regular languages
Pumping Lemma: Let L be a regular language. There exists an integer p (“pumping length”) for which every w ∈ L with |w| ≥ p can be written as
w = xyz such that 1. for every i ≥0, xyiz ∈L , and
2. |y|>0,and 3. |xy|≤p.
March 6, 2024 CS21 Lecture 26 26
Pumping Lemma for CFLs
CFL Pumping Lemma: Let L be a CFL. There exists an integer p (“pumping length”) for which every w ∈ L with |w| ≥
p can be written as
w = uvxyz such that
1. for every i ≥0, uvixyiz ∈L , and 2. |vy|>0,and
3. |vxy|≤p.
March 6, 2024 CS21 Lecture 26 27
Part II: Turing Machines and decidability
March 6, 2024 CS21 Lecture 26 28
Turing Machines
input tape
011001110100 …
read/write head
• New capabilities:
– infinite tape
– can read OR write to tape
– read/write head can move left and right
March 6, 2024 CS21 Lecture 26 29
finite control
Deciding and Recognizing
• accept input machine • reject
• TM M: • loop forever
– L(M) is the language it recognizes
– if M rejects every x ∉ L(M) it decides L
– set of languages recognized by some TM is called Turing-recognizable or recursively enumerable (RE)
– set of languages decided by some TM is called Turing-decidable or decidable or recursive
March 6, 2024 CS21 Lecture 26 30
Church-Turing Thesis
• the belief that TMs formalize our intuitive notion of an algorithm is:
• Note: this is a belief, not a theorem.
March 6, 2024 CS21 Lecture 26 31
The Church-Turing Thesis
everything we can compute on a physical computer
can be computed on a Turing Machine
The Halting Problem
Turing Machines
H’: n Y n Y Y n Y
March 6, 2024 CS21 Lecture 26
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.
Decidable, RE, coRE…
{anbn : n ≥ 0 }
co-HALT some language
all languages
decidable co-RE
regular languages
context free languages
{anbncn:n≥0} HALT
some problems (e.g HALT) have no algorithms
March 6, 2024 CS21 Lecture 26 33
Definition of reduction
• More refined notion of reduction:
– “many-one” reduction (commonly) – “mapping” reduction (book)
CS21 Lecture 26
reduction from f no language A to
March 6, 2024
language B
Using reductions
• Used reductions to prove lots of problems were:
– undecidable (reduce from undecidable) – non-RE (reduce from non-RE)
• or show undecidable, and coRE
– non-coRE (reduce from non-coRE)
• or show undecidable, and RE
Rice’s Theorem: Every nontrivial TM
property is undecidable.
March 6, 2024 CS21 Lecture 26 35
The Recursion Theorem
Theorem: Let T be a TM that computes fn: t: Σ* x Σ* → Σ*
There is a TM R that computes the fn:
r: Σ* → Σ*
defined as r(w) = t(w,
• In the course of computation, a Turing
Machine can output its own description. March 6, 2024 CS21 Lecture 26 36
Summary Part III: Complexity
March 6, 2024 CS21 Lecture 26 37
Complexity
• Complexity Theory = study of what is computationally feasible (or tractable) with
limited resources:
– running time
– storage space
– number of random bits – degree of parallelism – rounds of interaction
– others…
March 6, 2024 CS21 Lecture 26
main focus
not in this course
Time and Space Complexity Definition: the time complexity of a TM M is a
March 6, 2024 CS21 Lecture 26 39
number of steps M uses on any input of length n.
N, where f(n) is the maximum Definition: the space complexity of a TM M is a
function f:
number of tape cells M scans on any input of length n.
function f:
N, where f(n) is the maximum
Complexity Classes
Definition: TIME(t(n)) = {L : there exists a TM M that decides L in time O(t(n))}
P = ∪k ≥ 1 TIME(nk)
EXP = ∪k ≥ 1 TIME(2nk) Definition: SPACE(t(n)) = {L : there exists a
TM M that decides L in space O(t(n))}
PSPACE= ∪k ≥ 1 SPACE(nk)
March 6, 2024 CS21 Lecture 26 40
Complexity Classes Definition: NTIME(t(n)) = {L : there exists a
NTM M that decides L in time O(t(n))} NP= ∪k ≥ 1 NTIME(nk)
• Theorem: P ⊆ EXP
• P ⊆NP ⊆PSPACE ⊆EXP
• Don’t know if any of the containments are
March 6, 2024 CS21 Lecture 26 41
Alternate definition of NP
Theorem: language L is in NP if and only if it is expressible as:
L = { x | ∃ y, |y| ≤ |x|k, (x, y) ∈ R } where R is a language in P.
March 6, 2024 CS21 Lecture 26 42
Poly-time reductions
• Type of reduction we will use:
– “many-one” poly-time reduction (commonly) – “mapping” poly-time reduction (book)
March 6, 2024
yes f yes no f no
CS21 Lecture 26
1. f poly-time computable
2. YES maps to YES
3. NO maps to NO
Hardness and completeness
Definition: a language L is C-hard if for every language A ∈ C, A poly-time reduces to L; i.e., A ≤P L.
can show L is C-hard by reducing from a known C-hard problem
Definition: a language L is C-complete if L is C-hard and L ∈ C
March 6, 2024 CS21 Lecture 26 44
Complete problems
• EXP-complete: ATMB = {
TM that accepts x within at most m steps}
• PSPACE-complete: QSAT = {φ : φ is a 3- CNF, and ∃x1∀x2∃x3… ∀xn φ(x1, x2, … xn) }
• NP-complete: 3SAT = {φ : φ is a satisfiable 3-CNF formula}
March 6, 2024 CS21 Lecture 26 45
Lots of NP-complete problems
• Indendent Set
• Vertex Cover
• Hamilton Path (directed and undirected)
• Hamilton Cycle and TSP
• Subset Sum
• Problem sets: max/min Bisection, 3-coloring, subgraph
isomorphism, subset sum, (3,3)-SAT, Partition, Knapsack, Max2SAT…
March 6, 2024 CS21 Lecture 26 46
Other complexity classes
• coNP – complement of NP
– complete problems: UNSAT, DNF-TAUTOLOGY
• NP intersect coNP
– contains (decision version of ) FACTORING
– complete problems: QSAT, GEOGRAPHY
March 6, 2024 CS21 Lecture 26 47
Complexity classes
decidable languages
all containments believed to be proper March 6, 2024 CS21 Lecture 26 48
Quantum Computation
March 6, 2024 CS21 Lecture 26 49
Extended Church-Turing Thesis
• the belief that TMs formalize our intuitive notion of an efficient algorithm is:
• Quantumcomputationchallengesthisbelief
March 6, 2024 CS21 Lecture 26 50
The “extended” Church-Turing Thesis
everything we can compute in time t(n) on a physical computer can be computed on a (probabilistic)Turing Machine in time t(n)O(1) (polynomial slowdown)
For use later… • Fourier transform:
time domain
time domain
frequency domain
can recover r from position
March 6, 2024
CS21 Lecture 26
frequency domain
A different model
• infinite tape of a Turing Machine is an idealized model of computer
• real computer is a Finite Automaton (!) – n bits of memory
–2n states
March 6, 2024 CS21 Lecture 26 52
Model of deterministic computation
one 1 per column
state at state at time t time t+1
March 6, 2024 CS21 Lecture 26
2n possible
basic states
Model of randomized computation
possible states at time t:
∑!𝑝!=1 pi∈R+
state at state at time t time t+1
March 6, 2024 CS21 Lecture 26
“stochastic matrix ” sum in each column = 1
Model of randomized computation
• at end of computation, see specific state
• demand correct result with high probability • think of as “measuring” system:
March 6, 2024 CS21 Lecture 26 55
see ith basic state with probability pi
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com