CS21 Decidability and Tractability
Lecture 25 March 4, 2024
• Challenges to Extended Church-Turing – randomized computation
– quantum computation
Copyright By PowCoder代写 加微信 powcoder
March 4, 2024 CS21 Lecture 25 2
Extended Church-Turing Thesis
• the belief that TMs formalize our intuitive notion of an efficient algorithm is:
• randomizedcomputationchallengesthisbelief March 4, 2024 CS21 Lecture 25 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)
Randomness in computation
• Example of the power of randomness • Randomized complexity classes
March 4, 2024 CS21 Lecture 25 4
Communication complexity
Theorem: no deterministic protocol can compute EQ(x, y) while exchanging fewer than n+1 bits.
– “input matrix”:
Y = {0,1}n
X = {0,1}n
CS21 Lecture 25
March 4, 2024
Communication complexity
• Can we do better?
– deterministic protocol? – probabilistic protocol?
• at each step: one party sends bits that are a function of held input and received bits so far and the result of some coin tosses
• required to output f(x, y) with high probability over all coin tosses
March 4, 2024 CS21 Lecture 25 6
Communication complexity
• protocol for EQ employing randomness?
– Alice picks random prime p in {1…4n2}, sends:
• (x mod p)
– Bob sends:
• (y mod p)
– players output 1 if and only if:
(x mod p) = (y mod p)
March 4, 2024 CS21 Lecture 25 7
Communication complexity
– O(log n) bits exchanged
– if x = y, always correct
– if x ≠ y, incorrect if and only if:
p divides |x – y|
– # primes in range is ≥ 2n
– # primes dividing |x – y| is ≤ n – probability incorrect ≤ 1/2
Randomness gives an exponential advantage!!
March 4, 2024 CS21 Lecture 25 8
Communication complexity
• Goal:computef(x,y)whilecommunicatingas few bits as possible between Alice and : EQ(x, y) = 1 iff x = y
• Deterministicprotocol:nofewerthann+1bits
• Randomizedprotocol:O(logn)bits
March 4, 2024 CS21 Lecture 25 9
two parties: Alice and Bob function f:{0,1}n x {0,1}n → {0,1} Alice holds x ∈ {0,1}n; Bob holds y ∈ {0,1}n
Extended Church-Turing Thesis • Common to insert “probabilistic”:
March 4, 2024 CS21 Lecture 25 10
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)
Randomized complexity classes
• model: probabilistic Turing Machine
– deterministic TM with additional read-only
tape containing “coin flips”
finite control
input tape
011001110100 …
read/write head read head
011001110100 …
March 4, 2024
CS21 Lecture 25 11
Randomized complexity classes
• RP (Random Polynomial-time)
– L ∈ RP if there is a p.p.t. TM M:
x ∈ L → Pry[M(x,y) accepts] ≥ 1⁄2
x ∉ L → Pry[M(x,y) rejects] = 1
• coRP (complement of Random Polynomial-time) – L ∈ coRP if there is a p.p.t. TM M:
x ∈ L → Pry[M(x,y) accepts] = 1
x ∉ L → Pry[M(x,y) rejects] ≥ 1⁄2
“p.p.t” = probabilistic polynomial time
March 4, 2024 CS21 Lecture 25 12
Randomized complexity classes
• BPP (Bounded-error Probabilistic Poly-time) – L ∈ BPP if there is a p.p.t. TM M:
x ∈ L → Pry[M(x,y) accepts] ≥ 2/3 x ∉ L → Pry[M(x,y) rejects] ≥ 2/3
March 4, 2024 CS21 Lecture 25 13
Randomized complexity classes
One more important class:
• ZPP (Zero-error Probabilistic Poly-time) – ZPP = RP ∩ coRP
– Pry[M(x,y) outputs “fail”] ≤ 1⁄2
– otherwise outputs correct answer
March 4, 2024 CS21 Lecture 25 14
These classes may capture “efficiently computable” better than P.
RP,coRP, BPP
P ZPP coRP RPBPP PSPACE EXP
• from definitions: ZPP ⊆ RP, coRP ⊆ BPP
March 4, 2024 CS21 Lecture 25 15
Relationship to other classes
• all these classes contain P
– they can simply ignore the tape with coin flips
• allareinPSPACE
– can exhaustively try all strings y
– count accepts/rejects; compute probability
• RP ⊆ NP (and coRP ⊆ coNP)
– multitude of accepting computations – NP requires only one
March 4, 2024 CS21 Lecture 25 16
Polynomial identity testing
• Given: polynomial p(x1, x2, …, xn) as
arithmetic formula (fan-out 1):
x1 x2x3 …xn
variables take values in finite field F March 4, 2024 CS21 Lecture 25 17
• multiplication (fan-in 2) • addition (fan-in 2)
• negation (fan-in 1)
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 4, 2024 CS21 Lecture 25 18
Polynomial identity testing
• try all |F|n inputs?
– may be exponentially many
• multiply out symbolically, check that all coefficients are zero?
– may be exponentially many coefficients
• Best known deterministic algorithm places in EXP
March 4, 2024 CS21 Lecture 25 19
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 4, 2024 CS21 Lecture 25 20
Polynomial identity testing • Given: polynomial p(x1, x2, …, xn) over
• Is p identically zero?
-* *+- x1 x2x3 …xn
• Note: degree d is at most the size of input
March 4, 2024 CS21 Lecture 25 21
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 4, 2024 CS21 Lecture 25 22
Randomized complexity classes • We have shown:
– Polynomial Identity Testing is in coRP
– note: no sub-exponential time deterministic algorithm know
March 4, 2024 CS21 Lecture 25 23
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 4, 2024 CS21 Lecture 25 24
Is randomness a panacea for intractability?
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com