Complexity Theory Insights: CoNL and NL Immerman-Szelepcs.nyi Theorem
Delve into the intricacies of complexity theory with a focus on CoNL and NL, exploring key theorems like the Immerman-Szelepcs.nyi Theorem and discussing log-space reducibility, Time and Space Hierarchy Theorems, and more through detailed proofs and examples.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
18.404/6.840 Lecture 21 Last time: - Log-space reducibility - L = NL? question - ???? is NL-complete - 2??? is NL-complete - NL = coNL (unfinished) Today: (Sipser 9.1) - Finish NL = coNL - Time and Space Hierarchy Theorems
NL = coNL (part 1/4) Theorem (Immerman-Szelepcs nyi): NL = coNL Proof: Show ???? NL Defn: NTM ? computes function ?: if for all ? 1) All branches of ? on ? halt with ? ? on the tape or reject. 2) Some branch of ? on ? does not reject. Theorem: If some NL-machine (log-space NTM) computes ??? , then some NL-machine computes ?. Proof: On input ?,? 1. Let ? 0 2. For each node ? 3. If ??? ?,?,? = YES, then ? ? + 1 4. If ??? ?,?,? = NO, then continue 5. Output ? (d) 5 (h) 9 Check-in 21.1 Let ? be the graph below. What is the value of ? = ? ?,? ? (a) 2 (e) 6 (b) 3 (f) 7 (c) 4 (g) 8 YES, if ? has a path from ? to ? NO, if not Let ??? ?,?,? = Let ? = ? ?,? = ? ??? ?,?,? = YES} Let ? = ? ?,? = |?| ? ? = ? ? ? ? = Reachable nodes ? = # reachable Next: Converse of above ? = |?| Check-in 21.1
NL = coNL (part 2/4) key idea Theorem: If some NL-machine computes ?, then some NL-machine computes ??? . Proof: On input ?,?,? where ? has ? nodes 1. Compute ? 2. ? 0 3. For each node ? 4. Nondeterministically go to (p) or (n) (p) Nondeterministically pick a path from ? to ? of length ?. If fail, then reject. If ? = ?, then output YES, else set ? ? + 1. (n) Skip ? and continue. 5. If ? ? then reject. 6. Output NO. [found all ? reachable nodes and none were ?} ? ? ? ? = |?|
NL = coNL (part 2/4) key idea SIMPLIFIED!! Theorem: If some NL-machine computes ?, then some NL-machine computes ??? . Proof: On input ?,?,? where ? has ? nodes 1. Compute ? 2. ? 0 3. For each node ? 4. Nondeterministically pick a path from ? of length ?. If it ends at ? then output YES and stop. If it ends at ?, set ? ? + 1. 5. If ? ? then reject. 6. Output NO. [found all ? reachable nodes and none were ?} ? ? ? ? = |?|
NL = coNL (part 3/4) YES, if ? has a path ? to ? of length ? NO, if not Let ??? ??,?,? = Let ??= ???,? = ? ??? ??,?,? = YES} Let ??= ???,? = |??| Theorem: If some NL-machine computes ??, then some NL-machine computes ??? ?. Proof: On input ?,?,? 1. Compute ?? 2. ? 0 3. For each node ? 4. Nondeterministically go to (p) or (n) (p) Nondeterministically pick a path from ? to ? of length ?. If fail, then reject. If ? = ?, then output YES, else set ? ? + 1. (n) Skip ? and continue. 5. If ? ?? then reject. 6. Output NO [found all ?? reachable nodes and none were ?} ?? ? ? ??= |??|
NL = coNL (part 4/4) Theorem: If some NL-machine computes ??, then some NL-machine computes ??? ?+1. Proof: On input ?,?,? 1. Compute ? 2. ? 0 3. For each node ? 4. Nondeterministically go to (p) or (n) (p) Nondeterministically pick a path from ? to ? of length ?. If fail, then reject. If ? has an edge to ?, then output YES, else set ? ? + 1. (n) Skip ? and continue. 5. If ? ?? then reject. 6. Output NO. [found all ?? reachable nodes and none had an edge to ?} ?? ??+1 ? ? ??= |??| ??+1= |??+1| Hence ???? NL On input ?,?,? 1. ?0= 1. 2. Compute each ??+1 from ?? for ? = 1 to ?. 3. Accept if ??? ?(?,?,?) = NO. 4. Reject if ??? ?(?,?,?) = YES. Corollary: Some NL-machine computes ??+1 from ??.
Review: Major Complexity Classes L NL P NP PSPACE Today The time and space hierarchy theorems show that if a TM is given more time (or space) then it can do more.* * certain restrictions apply. For example: TIME ?2 ,TIME ?3 [ ,means proper subset ] SPACE ?2 ,SPACE ?3
Space Hierarchy Theorem (1/2) Theorem: For any ?: (where ? satisfies a technical condition) there is a language ? where ? requires ? ? ? space, i.e, 1) ? is decidable in ? ? ? space, and 2) ? is not decidable in ? ? ? space ,SPACE ? ? = {?| some TM ? decides ? in space ? ? ? } On other words, SPACE ? ? ? Notation: SPACE ? ? ? Proof outline: (Diagonalization) Give TM ? where 1) ? runs in ? ? ? space 2) ? ensures that ?(?) ?(?) for every TM ? that runs in ? ? ? space. ? SPACE ? ? SPACE ? ? ? Let ? = ?(?).
Mark off ? ? tape Space Hierarchy Theorem (2/2) ? ? ? ? ? = 010110 10100000 # ? Hide me ? Goal: Exhibit ? SPACE ? ? but ? SPACE ? ? ? Give ? where ? = ?(?) and 1) ? runs in ? ? ? space 2) ? ensures that ?(?) ?(?) for every TM ? that runs in ? ? ? space. Issues: 1. What if ? runs in ? ? ? space but has a big constant? Then ?won t have space to simulate ? when ? is small. FIX: simulate ? on infinitely many ?. ? = On input ? 1. Mark off ?(?) tape cells where ? = |?|. If ever try to use more tape, reject. 2. If ? ? 10 for some TM ?, reject. 3. Simulate* ? on ? for 2? ? steps Accept if ? rejects, Reject if ? accepts or hasn t halted. *Note: ? can simulate ? with a constant factor space overhead. 2. What if ? loops? [? must always halt] FIX: Stop ? if it runs for 2? ? steps. What happens when we run ? on input ? 1000000 ? a) It loops b) It accepts c) It rejects d) We get a contradiction e) Smoke comes out Check-in 21.2 3. How to compute ?? FIX: Assume ? is space constructible, i.e., can compute ? within ?(? ? ) space. Nice functions like log?, log2?, ?, ?2, 2?, are all space constructible. Check-in 21.2
Time Hierarchy Theorem (1/2) Theorem: For any ?: where ? is time constructible there is a language ? where ? requires ? ? ? time, i.e, 1) ? is decidable in ? ? ? time, and 2) ? is not decidable in ? ? ? /log ? ? time ? ? ,TIME ? ? On other words, TIME ? log ? ? Proof outline: Give TM ? where 1) ? runs in ? ? ? time 2) ? ensures that ?(?) ?(?) for every TM ? that runs in ? ? ? /log ? ? time . Let ? = ?(?).
Time Hierarchy Theorem (2/2) Goal: Exhibit ? TIME ? ? but ? TIME ? ? ? /log ? ? ? = ?(?) where 1) ? runs in ? ? ? time 2) ? ensures that ?(?) ?(?) for every TM ? that runs in ? ? ? /log ? ? time. Why do we lose a factor of ??? ? ? ? ? must halt within ? ? ? time. To do so, ? counts the number of steps it uses and stops if the limit is exceeded. The counter has size log ? ? and is stored on the tape. It must be kept near the current head location. Cost of moving it adds a ? log ? ? factor. So to halt within ? ? ? time, ? stops when the counter reaches ? ? /log ? ? . ? = On input ? 1. Compute ?(?). 2. If ? ? 10 for some TM ?, reject. 3. Simulate* ? on ? for ? ? /log ? ? steps. Accept if ? rejects, Reject if ? accepts or hasn t halted. *Note: ? can simulate ? with a log factor time overhead due to the step counter. overhead
Recap: Separating Complexity Classes L NL P NP PSPACE Space Hierarchy Theorem NL SPACE log2 ? ,SPACE ? PSPACE Check-in 21.3 Consider these two famous unsolved questions: 1. Does L = P? 2. Does P = PSPACE? What do the hierarchy theorems tell us about these questions? a) Nothing b) At least one of these has answer NO c) At least one of these has answer YES Check-in 21.3
Quick review of today 1. Finish NL = coNL 2. Space hierarchy theorem 3. Time hierarchy theorem
