CS21 Decidability and Tractability
Lecture 23 February 28, 2024
• language L is in coNP iff its complement (co-L) is in NP
• it is believed that NP ≠ coNP
Copyright By PowCoder代写 加微信 powcoder
• note: P = NP implies NP = coNP
– proving NP ≠ coNP would prove P ≠ NP – another major open problem…
February 28, 2024 CS21 Lecture 23 2
• canonical coNP-complete language:
UNSAT = {φ : φ is an unsatisfiable 3-CNF formula}
February 28, 2024 CS21 Lecture 23 3
coNP • another example
3-DNF-TAUTOLOGY = {φ : φ is a 3-DNF formula and for all x, φ(x) =1}
• another example:
EQUIV-CIRCUIT = {(C1, C2) : C1 and C2 are Boolean circuits and for all x, C1(x) = C2(x)}
February 28, 2024 CS21 Lecture 23 4
Disjunctive Normal Form = OR of ANDs
Quantifier characterization of coNP
February 28, 2024 CS21 Lecture 23 5
Proof interpretation of coNP
“proof” “short” proof “proof verifier”
February 28, 2024 CS21 Lecture 23 6
• what complexity class do the following languages belong in?
– COMPOSITES = {x : integer x is a composite} – PRIMES = {x : integer x is a prime number}
– GRAPH-NONISOMORPHISM = {(G, H) : G
and H are graphs that are not isomorphic}
– EXPANSION = {(G = (V,E), 𝛼 > 0): every subset S ⊆ V of size at most |V|/2 has at least 𝛼|S| neighbors}
February 28, 2024 CS21 Lecture 23 7
• Picture of the way we believe things are:
decidable languages
February 28, 2024
NP ∩ coNP CS21 Lecture 23
• Might guess NP ∩ coNP = P by analogy
with RE (since RE ∩ coRE = DECIDABLE)
• Not believed to be true.
• A problem in NP ∩ coNP not believed to
L = {(x, k): integer x has a prime factor p < k}
(decision version of factoring)
February 28, 2024 CS21 Lecture 23 9
February 28, 2024 CS21 Lecture 23 10
PRIMES in NP
February 28, 2024 CS21 Lecture 23 11
• Picture of the way we believe things are:
(decision version of ) FACTORING
decidable languages
February 28, 2024
NP ∩ coNP CS21 Lecture 23
Space complexity
Definition: the space complexity of a TM M is a function
cells M scans on any input of length n.
• “M uses space f(n),” “M is a f(n) space TM” February 28, 2024 CS21 Lecture 23 13
where f(n) is the maximum number of tape
Space complexity
Definition: SPACE(t(n)) = {L : there exists a TM M that decides L in space O(t(n))}
PSPACE = ∪k ≥ 1 SPACE(nk)
February 28, 2024 CS21 Lecture 23 14
decidable languages
• NP ⊆ PSPACE, coNP ⊆ PSPACE (proof?) • PSPACE ⊆ EXP (proof?)
• containments believed to be proper
February 28, 2024 CS21 Lecture 23 15
• A PSPACE-complete problem: • Quantified Satisfiability:
QSAT = {φ : φ is a 3-CNF, and ∃x1∀x2∃x3∀x4∃x5... ∀xn φ(x1, x2, x3, ... xn) }
• example:φ=(x1∨x2 ∨¬x3)∧(¬x2 ∨¬x3) ∃x1 ∀x2 ∃x3 φ?
YES: x1=T; if x2=T, set x3=F; if x2=F, set x3=T February 28, 2024 CS21 Lecture 23 16
• A PSPACE-complete problem: • Quantified Satisfiability:
QSAT = {φ : φ is a 3-CNF, and ∃x1∀x2∃x3∀x4∃x5... ∀xn φ(x1, x2, x3, ... xn) }
• example:φ=(x1∨¬x2∨¬x3)∧(¬x2)
∃x1 ∀x2 ∃x3 φ?
NO: x1=T; if x2=T...; x1=F; if x2=T...
February 28, 2024 CS21 Lecture 23 17
QSAT is PSPACE-complete
Theorem: QSAT is PSPACE-complete. • Proof:
– 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
February 28, 2024 CS21 Lecture 23 18
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.
February 28, 2024 CS21 Lecture 23 19
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)
February 28, 2024 CS21 Lecture 23 20
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
February 28, 2024 CS21 Lecture 23 21
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com