CS21 Decidability and Tractability
Lecture 19 February 16, 2024
Grades so far
• An idea of eventual scale:
Copyright By PowCoder代写 加微信 powcoder
• 2024 so far: 80.0; 84.82
• 2023 mean 80.5; median 81.36
• 2022: mean 80.9; median 83.6
• 2021: mean 85.7; median 86.9
• 2020: mean 81.3; median 81.8
February 16, 2024
97.5 100 A+ 89.5 97.5 A 86.5 89.5 A- 83.5 86.5 B+ 78.5 83.5 B 73.5 78.5 B- 69.5 73.5 C+ 65.5 69.5 C
61 65.5 C- 56.5 61D+ 51.5 56.5 D
0 51.5 E/F
CS21 Lecture 19
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 16, 2024 CS21 Lecture 19 3
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 16, 2024 CS21 Lecture 19 4
Poly-time verifiers
• NP = {L : L decided by poly-time NTM}
• Very useful alternate definition of NP:
“witness” or “certificate”
efficiently Theorem: language L is in NP if avnedrifoianbllye if
it is expressible as:
L = { x | ∃ y, |y| ≤ |x|k, (x, y) ∈ R } where R is a language in P.
• poly-time TM MR deciding R is a “verifier” February 16, 2024 CS21 Lecture 19 5
Poly-time verifiers • Example: 3SAT expressible as
3SAT = {φ : φ is a 3-CNF formula for which ∃ assignment A for which (φ, A) ∈ R}
R = {(φ, A) : A is a sat. assign. for φ}
– satisfying assignment A is a “witness” of the satisfiability of φ (it “certifies” satisfiability of φ)
– R is decidable in poly-time
February 16, 2024 CS21 Lecture 19 6
Poly-time verifiers
L = { x | ∃ y, |y| ≤ |x|k, (x, y) ∈ R } Proof: (⇐) give poly-time NTM deciding L
phase 1: “guess” y with |x|k nondeterministic steps
phase 2: decide if (x, y) ∈R
February 16, 2024 CS21 Lecture 19 7
Poly-time verifiers Proof: (⇒) given L ∈ NP, describe L as:
L = { x | ∃ y, |y| ≤ |x|k, (x, y) ∈ R }
– L is decided by NTM M running in time nk – define the language
R = { (x, y) : y is an accepting computation history of M on input x}
– check: accepting history has length ≤ |x|k
– check: M accepts x iff ∃ y, |y| ≤ |x|k, (x, y) ∈ R
February 16, 2024 CS21 Lecture 19 8
• Gateway to proving lots of natural, important problems NP-complete is:
Theorem (Cook, Levin): 3SAT is NP- complete.
• Recall: 3SAT = {φ : φ is a CNF formula with 3 literals per clause for which there exists a satisfying truth assignment}
February 16, 2024 CS21 Lecture 19 9
• Proof outline
– show CIRCUIT-SAT is NP-complete
CIRCUIT-SAT = {C : C is a Boolean circuit for which there exists a satisfying truth
assignment}
– show 3SAT is NP-complete (reduce from CIRCUIT SAT)
February 16, 2024 CS21 Lecture 19 10
Boolean Circuits
• Boolean circuit C
– directed acyclic graph
– nodes: AND (∧); OR (∨); NOT (¬); variables xi
x1 x2x3 …xn
• C computes function f:{0,1}n → {0,1} in natural way
– identify C with function f it computes
• size = # nodes
February 16, 2024 CS21 Lecture 19 11
Boolean Circuits
• every function f:{0,1}n → {0,1} computable by a circuit of size at most O(n2n)
– AND of n literals for each x such that f(x) = 1 – OR of up to 2n such terms
February 16, 2024 CS21 Lecture 19 12
CIRCUIT-SAT is NP-complete Theorem: CIRCUIT-SAT is NP-complete
CIRCUIT-SAT = {C : C is a Boolean circuit for which there exists a satisfying truth assignment}
– Part 1: need to show CIRCUIT-SAT ∈ NP.
• can express CIRCUIT-SAT as:
CIRCUIT-SAT = {C : C is a Boolean circuit for which ∃x such that (C, x) ∈ R}
R = {(C, x) : C is a Boolean circuit and C(x) = 1} February 16, 2024 CS21 Lecture 19 13
CIRCUIT-SAT is NP-complete
CIRCUIT-SAT = {C : C is a Boolean circuit for which there exists a satisfying truth assignment}
– Part 2: for each language A ∈ NP, need to
give poly-time reduction from A to CIRCUIT-SAT
– for a given language A ∈ NP, we know
A = {x | ∃ y, |y| ≤ |x|k, (x, y) ∈ R } and there is a (deterministic) TM MR that decides R in time g(n) ≤ nc for some c.
February 16, 2024 CS21 Lecture 19 14
CIRCUIT-SAT is NP-complete
• Tableau (configurations written in an array) for machine MR on input w = (x, y):
• height = time taken =|w|c
• width = spaceused ≤ |w|c
w1/qsw2 …wn…_ w1w2/q1…wn…_ w1/q1 a … wn … _
. . _/qa _ … _ … _
February 16, 2024 CS21 Lecture 19
CIRCUIT-SAT is NP-complete
• Important observation: contents of cell in tableau determined by 3 others above it:
a/q1 b a b/q1
February 16, 2024
a b/q1 a a
CS21 Lecture 19
CIRCUIT-SAT is NP-complete
• Can build Boolean circuit STEP – input (binary encoding of) 3 cells – output (binary encoding of) 1 cell
a b/q1 STEP
a • each output bit is some function of inputs
February 16, 2024
• can build circuit for each • size is independent of
size of tableau
CS21 Lecture 19 17
CIRCUIT-SAT is NP-complete
Tableau for MR on input w = (x, y)
w1/qs w2 w1 w2/q1
… _ … _
• |w|c copies of STEP compute row i from i-1
STEP STEP STEP STEP
February 16, 2024 CS21 Lecture 19
CIRCUIT-SAT is NP-complete
w1/qs w2 … wn … _ STEP STEP STEP STEP STEP
STEP STEP STEP STEP STEP . .
STEP STEP STEP STEP STEP
ignore these
1 iff cell contains qaccept
February 16, 2024 CS21 Lecture 19 19
This circuit CMR, w has inputs w1w2…wn
and C(w) = 1 iff MR accepts input w.
Size = O(|w|2c)
CIRCUIT-SAT is NP-complete
– recall: we are reducing language A:
A = { x | ∃ y, |y| ≤ |x|k, (x, y) ∈ R } to CIRCUIT-SAT.
– f(x) produces the following circuit:
x1 x2 … xn y1 y2 … ym
– hardwire input x
– leave y as
1 iff (x,y) ∈ R February 16, 2024
variables Circuit CMR, w
CS21 Lecture 19
CIRCUIT-SAT is NP-complete
– is f(x) poly-time computable?
• hardcode MR, k and c
• circuit has size O(|w|2c); |w| = |(x,y)| ≤ n + nk
• each component easy to describe efficiently from description of MR
– YES maps to YES?
•x∈A⇒∃y,MRaccepts (x,y)⇒f(x)∈CIRCUIT-SAT – NO maps to NO?
• x∉A⇒∀y, MR rejects (x, y) ⇒ f(x)∉ CIRCUIT-SAT February 16, 2024 CS21 Lecture 19 21
3SAT is NP-complete Theorem: 3SAT is NP-complete
3SAT = {φ : φ is a 3-CNF formula for which there exists a satisfying truth assignment}
– Part 1: need to show 3-SAT ∈ NP
• already done
– Part 2: need to show 3-SAT is NP-hard
• we will give a poly-time reduction from CIRCUIT-SAT to 3-SAT
February 16, 2024 CS21 Lecture 19 22
3SAT is NP-complete
– given a circuit C
• variables x1, x2, …, xn
• AND (∧), OR (∨), NOT (¬) gates g1, g2, …, gm
– reduction f(C) produces these clauses for φ on variables x1, x2, …, xn, g1, g2, …, gm:
z February 16, 2024
• (gi ∨ z)
(z ⇔ ¬gi) CS21 Lecture 19 23
• (¬z ∨ ¬gi)
3SAT is NP-complete
– given a circuit C
• variables x1, x2, …, xn
• AND (∧), OR (∨), NOT (¬) gates g1, g2, …, gm
– reduction f(C) produces these clauses for φ on variables x1, x2, …, xn, g1, g2, …, gm:
z1 z2 February 16, 2024
• (¬z1 ∨ gi)
• (¬z2 ∨ gi)
• (¬gi ∨ z1 ∨ z2) CS21 Lecture 19
(z1∨z2 ⇔ gi)
3SAT is NP-complete
– given a circuit C
• variables x1, x2, …, xn
• AND (∧), OR (∨), NOT (¬) gates g1, g2, …, gm
– reduction f(C) produces these clauses for φ on variables x1, x2, …, xn, g1, g2, …, gm:
z1 z2 February 16, 2024
• (¬gi ∨ z1)
• (¬gi ∨ z2)
• (¬z1 ∨ ¬z2 ∨gi) CS21 Lecture 19
(z1 ∧ z2 ⇔ gi)
3SAT is NP-complete
– finally, reduction f(C) produces single clause
(gm) where gm is the output gate. – f(C) computable in poly-time?
• yes, simple transformation
– YES maps to YES?
• if C(x) = 1, then assigning x-values to x- variables of φ and gate values of C when evaluating x to the g-variables of φ gives satsifying assignment.
February 16, 2024 CS21 Lecture 19 26
3SAT is NP-complete
– NO maps to NO?
• show that φ satisfiable implies C satisfiable
• satisfying assignment to φ assigns values
to x-variables and g-variables
• output gate gm must be assigned 1
• every other gate must be assigned value it
would take given values of its inputs.
• the assignment to the x-variables must be a satisfying assignment for C.
February 16, 2024 CS21 Lecture 19 27
Search vs. Decision
• Definition: given a graph G = (V, E), an independent set in G is a subset V’⊆ V suchthatforallu,w∈V’ (u,w)∉E
• A problem:
given G, find the largest independent set
• This is called a search problem
– searching for optimal object of some type – comes up frequently
February 16, 2024 CS21 Lecture 19 28
Search vs. Decision
• We want to talk about languages (or
decision problems)
• Most search problems have a natural, related decision problem by adding a bound “k”; for example:
– search problem: given G, find the largest independent set
– decision problem: given (G, k), is there an
independent set of size at least k
February 16, 2024 CS21 Lecture 19 29
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com