�ݺ�ߣ

Theory of Computation – Lecture 16
MARCH 25 2021
1
- PSPACE Completeness (Sipser 8.3)
- L and NL (Sipser 8.4, 8.5)
Some material from slides by M. Sipser

Announcements
 UPE Announcement
 No class on Thursday, April 1.
2

Exam 2
 Monday, March 29, 2021
 Will be given through Gradescope.
 Available 12pm – 8pm NY Time. You will have 2 hours.
 Exam is open book and open notes. No collaboration. No posting questions or searching for
solutions online.
 Exam is not cumulative, but will use concepts from pre-Exam 1 (e.g., DFAs, NFAs, TMs, Regular
Expressions, Turing recognizability, decidability)
 Similar to the way we have used these topics in class and on homework problems.
3

Exam 2 Topics
 Chapter 4: Undecidability (Section 4.2)
 Chapter 5: Reducibility, Mapping Reducibility
 No questions on the Post Correspondence Problem
 Chapter 6: The Recursion Theorem (Section 6.1)
 Both the proof and applications of the theorem
 Chapter 7: The classes TIME(t(n)), NTIME(t(n)), P, NP, polynomial time reductions, NP-completeness, the
Cook-Levin Theorem
 Also refresh your memory on problems: SAT, 3SAT, CLIQUE, PATH, HAMPATH
 Chapter 8: Savitch’s Theorem, PSPACE, NPSPACE, PSPACE-completeness
 No questions on Sections 8.4 – 8.6.
4

Review – Space Complexity Classes
 Deterministic TM
 The space complexity of M is a function 𝑓: ℕ→ℕ with 𝑓(𝑛)≥𝑛, where 𝑓(𝑛) is the maximum number of
tape cells M accesses on any input of length 𝑛.
 𝑆𝑃𝐴𝐶𝐸(𝑓(𝑛)) is the set of languages that are are decidable in 𝑂(𝑓(𝑛)) space.
 𝑃𝑆𝑃𝐴𝐶𝐸 = ∪𝑘 𝑆𝑃𝐴𝐶𝐸 𝑛𝑘
 Nondeterministic TM
 The space complexity of N is a function 𝑓: ℕ→ℕ with 𝑓(𝑛)≥𝑛, where 𝑓(𝑛) is the maximum number of
tape cells N accesses on a single computation path on any input of length 𝑛.
 𝑁𝑆𝑃𝐴𝐶𝐸(𝑓(𝑛)) is the set of languages that are decidable in 𝑂(𝑓(𝑛)) space.
 𝑁𝑃𝑆𝑃𝐴𝐶𝐸 = ∪𝑘 𝑁𝑆𝑃𝐴𝐶𝐸 𝑛𝑘
5

Review 1 – Relationship Between Space and Time Complexity
 Theorem:
1) 𝑇𝐼𝑀𝐸(𝑡(𝑛)) ⊆ 𝑆𝑃𝐴𝐶𝐸(𝑡(𝑛))
2) 𝑆𝑃𝐴𝐶𝐸(𝑡(𝑛)) ⊆ 𝑇𝐼𝑀𝐸(2𝑂 𝑡 𝑛 ) = ⋃𝑐 𝑇𝐼𝑀𝐸 (𝑐𝑡 𝑛 )
6

 Theorem: 𝑃 ⊆ 𝑁𝑃 ⊆ 𝑃𝑆𝑃𝐴𝐶𝐸
7

Review– Savitch’s Theorem
 Theorem: For any function 𝑓 𝑛 : ℕ → ℝ+
where 𝑓 𝑛 ≥ 𝑛, 𝑁𝑆𝑃𝐴𝐶𝐸 𝑓 𝑛 ⊆ 𝑆𝑃𝐴𝐶𝐸(𝑓2
𝑛 ).
 Proof idea: : Convert NTM 𝑁 to equivalent TM 𝑀, only squaring the space used.
 𝑀: On input (𝑐𝑖, 𝑐𝑗, 𝑡)
 1. If 𝑡 = 1, check if 𝑐𝑗 can be reached from 𝑐𝑖 using 𝑁’s transition function in 0 or 1 steps. Accept if yes; otherwise,
reject.
 2. If 𝑡 > 1, repeat for all configurations 𝑐𝑚 that use 𝑓(𝑛) space.
 3. Recursively test (𝑐𝑖, 𝑐𝑚, 𝑡/2) and (𝑐𝑚, 𝑐𝑗,
𝑡
2
)
 4. If both accept, then accept. If not, continue.
 5. Reject if haven’t yet accepted.
 Test if 𝑁 accepts 𝑤 by testing 𝑀 on input 𝑐𝑠𝑡𝑎𝑟𝑡, 𝑐𝑎𝑐𝑐𝑒𝑝𝑡, 𝑡 where 𝑡 = number of configurations
8

 As a result of Savitch’s theorem: 𝑃𝑆𝑃𝐴𝐶𝐸 = 𝑁𝑃𝑆𝑃𝐴𝐶𝐸
 What we’ve learned so far: 𝑃 ⊆ 𝑁𝑃 ⊆ 𝑃𝑆𝑃𝐴𝐶𝐸 = 𝑁𝑃𝑆𝑃𝐴𝐶𝐸 ⊆ 𝐸𝑋𝑃𝑇𝐼𝑀𝐸
10

PSPACE Completeness
 A language 𝐵 is PSPACE-complete if:
 1. 𝐵 ∈ 𝑃𝑆𝑃𝐴𝐶𝐸
 2. For all 𝐴 ∈ 𝑃𝑆𝑃𝐴𝐶𝐸, 𝐴 ≤𝑝 𝐵
 We will show that TQBF is PSPACE-Complete
11
Think of complete problems as the “hardest”
in their associated class.
NP
P
PSPACE =
NPSPACE
NP-complete
PSPACE-complete

TQBF is PSPACE-Complete
 Recall: 𝑇𝑄𝐵𝐹 = 𝜙 𝜙 is a QBF that is TRUE}
 Last lecture – we showed TQBF is in PSPACE.
 Gave a recursive algorithm that “peels off” one quantifier at each level of recursion.
 Each level uses 𝑂(1) space; the recursion depth is ≤ 𝑛.
 Now – we will give a polynomial time reduction from arbitrary language 𝐴 ∈ 𝑃𝑆𝑃𝐴𝐶𝐸 to 𝑇𝑄𝐵𝐹.
12

13
CONSTRUCTING 𝜙- FIRST ATTEMPT
Constructing 𝝓 - First Attempt
 Use approach like in proof of Cook-Levin theorem.
 Construct formula 𝜙 that matches an accepting tableau.
𝑞0 𝑤1 𝑤2 𝑤3 ⋯ 𝑤𝑛
a 𝑞7 𝑤2 ⋯
⋯ 𝑞accept ⋯

14
CONSTRUCTING 𝜙- SECOND ATTEMPT
Constructing 𝝓 - Second Attempt
 Use an approach like in Proof of Savitch’s Theorem – divide and conquer
 Encode contents of configuration cells (from tableau) as Boolean expression like in Cook-Levin theorem
 Recursively construct 𝜙𝑐𝑠𝑡𝑎𝑟𝑡,𝑐𝑎𝑐𝑐𝑒𝑝𝑡,𝑡 like in Savitch’s theorem

15
CONSTRUCTING 𝜙- SECOND ATTEMPT
Constructing 𝝓 - Third Attempt
 Use an approach like in proof of Savitch’s Theorem – divide and conquer
 Encode contents of configuration cells (from tableau) as Boolean expression like in Cook-Levin theorem
 Recursively construct 𝜙𝑐𝑠𝑡𝑎𝑟𝑡,𝑐𝑎𝑐𝑐𝑒𝑝𝑡,𝑡 like in Savitch’s theorem

Summary – So Far
16
NP
P
PSPACE =
NPSPACE
NP-complete
PSPACE-complete

Sublinear Space Complexity
 So far, we have studied space complexity bounds that are at least linear: 𝑓 𝑛 ≥ 𝑛.
 Are there problems that can be solved in sublinear space, 𝑓 𝑛 < 𝑛 ?
 To study sublinear space algorithms, we need a different model.
 Two-tape TM with read-only input tape and read/write work tape.
18
read-only input tape does not count towards space used
read/write work tape
count cells used here

Log Space Complexity
 We focus on algorithms with space complexity in O log 𝑛
 L is the class of languages that are decidable in logarithmic space on a deterministic TM:
𝐿 = 𝑆𝑃𝐴𝐶𝐸(log 𝑛)
 N is the class of languages that are decidable in logarithmic space on a nondeterministic TM:
𝑁𝐿 = 𝑁𝑆𝑃𝐴𝐶𝐸(log 𝑛)
19

Example in Class L
 𝐴 = 0𝑘1𝑘 𝑘 ≥ 0 }
20

Example in Class NL
 𝑃𝐴𝑇𝐻 = 𝐺, 𝑠, 𝑡 𝐺 is a directed graph that has a directed path from 𝑠 to 𝑡 }
21

Relationship to Other Complexity Classes
 Theorem: 𝑁𝐿 ⊆ 𝑃
 Theorem: NL ⊆ SPACE log2
𝑛
22

�ݺ�ߣ

Mar25.pptx

Recommended

More Related Content

Similar to Mar25.pptx (20)

Recently uploaded (20)

Mar25.pptx