CS21 Decidability and Tractability
Lecture 24 March 1, 2024
QSAT is PSPACE-complete
Theorem: QSAT is PSPACE-complete. • Proof:
Copyright By PowCoder代写 加微信 powcoder
– in PSPACE: ∃x1∀x2∃x3 … Qxn φ(x1, x2, …, xn)? – “∃x1”: for both x1 = 0, x1 = 1, recursively solve
∀x2∃x3 … Qxn φ(x1, x2, …, xn)?
• if at least one “yes”, return “yes”; else return “no”
– “∀x1”: for both x1 = 0, x1 = 1, recursively solve ∃x2∀x3 … Qxn φ(x1, x2, …, xn)?
• if at least one “no”, return “no”; else return “yes” – base case: evaluating a 3-CNF expression
– poly(n) recursion depth
– poly(n) bits of state at each level
March 1, 2024 CS21 Lecture 24 2
QSAT is PSPACE-complete
– given TM M deciding L ∈ PSPACE; input x – 2nk possible configurations
– single START configuration
– assume single ACCEPT configuration
REACH(X, Y, i) ⇔ configuration Y reachable from configuration X in at most 2i steps.
March 1, 2024 CS21 Lecture 24 3
QSAT is PSPACE-complete REACH(X, Y, i) ⇔ configuration Y reachable from
configuration X in at most 2i steps.
– Goal: produce 3-CNF φ(w1,w2,w3,…,wm) such that
∃w1∀w2 … ∃wm φ(w1,…,wm) ⇔ REACH(START, ACCEPT, nk)
March 1, 2024 CS21 Lecture 24 4
QSAT is PSPACE-complete
– for i = 0, 1, … nk produce quantified Boolean expressions ψi(A, B, W) such that ∀ A,B:
∃w1∀w2 … ψi(A, B, W) ⇔ REACH(A, B, i)
– convert ψnk to 3-CNF φ • add variables V
– hardwire A = START, B = ACCEPT
∃w1∀w2 …∃Vφ(W,V) ⇔ x∈L
March 1, 2024 CS21 Lecture 24 5
QSAT is PSPACE-complete
– ψo(A, B) = true iff
• AyieldsBinonestepofM
Boolean expression ofsizeO(nk)
STEP STEP STEP
March 1, 2024 CS21 Lecture 24
QSAT is PSPACE-complete – Key observation:
REACH(A, B, i+1)
∃Z[REACH(A, Z, i) ∧ REACH(Z, B, i)]
– cannot define ψi+1(A; B; Z, W, W’) to be
∃Z [∃w1∀w2 … ψi(A, Z, W) ∧ ∃w1’ ∀w2’… ψi(Z, B, W’) ] (why?)
March 1, 2024 CS21 Lecture 24 7
QSAT is PSPACE-complete – Key idea: use quantifiers
– couldn’t do ψi+1(A; B; Z, W, W’) =
∃Z [∃w1∀w2 … ψi(A, Z, W) ∧ ∃w1’ ∀w2’… ψi(Z, B, W’) ]
– define ψi+1(A; B; Z, X, Y, W) to be ∃Z∀X∀Y[((X=A ∧ Y=Z) ∨ (X=Z ∧ Y=B)) ⇒
∃w1∀w2 … ψi(X, Y, W)] – ψi(X, Y, W) is preceded by quantifiers
– move to front (they don’t involve X,Y,Z,A,B) March 1, 2024 CS21 Lecture 24 8
QSAT is PSPACE-complete ψo(A, B) = true iff A = B or A yields B in 1 step
ψi+1(A; B; Z, X, Y, W) =
∃Z∀X∀Y[((X=A ∧ Y=Z) ∨ (X=Z ∧ Y=B)) ⇒
∃w1∀w2 … ψi(X, Y, W)] – total size of ψnk is O(nk)2 = poly(n)
– reduction runs in polynomial time
March 1, 2024 CS21 Lecture 24 9
– |ψ0| = O(nk)
– |ψi+1| = O(nk) + |ψi|
PSPACE and games
QSAT = {φ : φ is a 3-CNF, and ∃x1∀x2∃x3∀x4∃x5… ∀xn φ(x1, x2, x3, … xn) }
• Think of as 2-player game (player 1 trying to satisfy φ; player 2 adversary):
– player 1 picks truth value for x1
– player 2 picks truth value for x2
– player 1 picks truth value for x3…
• φ ∈ QSAT iff player 1 can win no matter what player 2 does.
March 1, 2024 CS21 Lecture 24 10
PSPACE and games
• General phenomenon: many 2-player games are PSPACE-complete.
– 2 players I, II
– alternate pick-
pasadena athens
davis oakland
ing edges san
– lose when no francisco
unvisited choice
• GEOGRAPHY = {(G, s) : G is a directed graph and player I can win from node s}
March 1, 2024 CS21 Lecture 24 11
Theorem: GEOGRAPHY is PSPACE- complete.
– in PSPACE (proof?)
– PSPACE-hard. reduction from QSAT.
March 1, 2024 CS21 Lecture 24 12
GEOGRAPHY is PSPACE-complete • We are reducing from the language:
QSAT = {φ : φ is a 3-CNF, and ∃x1∀x2∃x3∀x4∃x5… ∀xn φ(x1, x2, x3, … xn) }
to the language:
GEOGRAPHY = {(G, s) : G is a directed graph and player I can win from node s}
March 1, 2024 CS21 Lecture 24 13
PSPACE ∃x1∀x2∃x3∀x4∃x5… ∀xn φ(x1, x2, x3, … xn)?
variable gadget for xi
March 1, 2024
clause choice gadget
… C1C2 Cm
CS21 Lecture 24
∃x1∀x2∃x3 …(¬x1∨x2∨ ¬x3)∧(¬x3∨x1)∧…∧(x1∨ ¬x2)
March 1, 2024
x1 false alternately pick truth assignment
x3 false I
CS21 Lecture 24
pick a clause
pick a true literal? 15
• Challenges to Extended Church-Turing – randomized computation
– quantum computation
March 1, 2024 CS21 Lecture 24 16
Extended Church-Turing Thesis
• the belief that TMs formalize our intuitive notion of an efficient algorithm is:
• randomizedcomputationchallengesthisbelief March 1, 2024 CS21 Lecture 24 17
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 1, 2024 CS21 Lecture 24 18
Communication complexity
• Goal:computef(x,y)whilecommunicatingas few bits as possible between Alice and Bob
• countnumberofbitsexchanged(computationfree) • ateachstep:onepartysendsbitsthatarea
function of held input and received bits so far
March 1, 2024 CS21 Lecture 24 19
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
Communication complexity • simple function (equality):
EQ(x, y) = 1 iff x = y
• simple protocol:
– Alice sends x to Bob (n bits)
– Bob sends EQ(x, y) to Alice (1 bit) – total: n + 1 bits
– (works for any predicate f)
March 1, 2024 CS21 Lecture 24 20
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 1, 2024 CS21 Lecture 24 21
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 24
March 1, 2024
Communication complexity
– assume 1 bit sent at a time (but proof works for general case)
– A sends 1 bit depending only on x:
Y = {0,1}n
X = {0,1}n
inputs x causing A to send 1
inputs x causing A to send 0
March 1, 2024
CS21 Lecture 24
Communication complexity
– B sends 1 bit depending only on y and received bit:
Y = {0,1}n
inputs y causing
March 1, 2024
CS21 Lecture 24
X = {0,1}n
B to send 1
inputs y causing B to send 0
Communication complexity
– at end of protocol involving k bits of communication, matrix is partitioned into at most 2k combinatorial rectangles
– bits sent in protocol are the same for every input (x, y) in given rectangle
– conclude: f(x,y) must be constant on each rectangle
March 1, 2024 CS21 Lecture 24 25
Communication complexity
Y = {0,1}n X = {0,1}n
– any partition into combinatorial rectangles with constant f(x,y) must have at least 2n + 1 rectangles – protocol that exchanges ≤ n bits can only create 2n
rectangles, so must exchange at least n+1 bits.
March 1, 2024 CS21 Lecture 24 26
Matrix for EQ:
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com