Understanding Space Complexity in Computational Theory
Delve into the concept of space complexity in computational theory, exploring the definitions, relationships with time complexity, and examples such as PSPACE and NPSPACE. Discover how multi-tape Turing machines impact space complexity and its implications in solving quantified Boolean formulas.
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 17 Last time: - Cook-Levin Theorem: ??? is NP-complete - 3??? is NP-complete Today: (Sipser 8.1 8.2) - Space complexity - SPACE ? ? , NSPACE ? ? - PSPACE, NPSPACE - Relationship with TIME classes - Examples 1
SPACE Complexity Defn: Let ?: where ? ? ?. Say TM ? runs in space ?(?) if ? always halts and uses at most ?(?) tape cells on all inputs of length ?. An NTM ? runs in space ?(?) if all branches halt and each branch uses at most ?(?) tape cells on all inputs of length ?. Check-in 17.1 We define space complexity for multi-tape TMs by taking the sum of the cells used on all tapes. Do we get the same class PSPACE for multi-tape TMs? (a) No. Defn: SPACE ? ? and ? runs in space ? ? ? } = {?| some deterministic 1-tape TM ? decides ? NSPACE ? ? and ? runs in space ? ? ? } = {?| some nondeterministic 1-tape TM ? decides ? (b) Yes, converting a multi-tape TM to single-tape only squares the amount of space used. (c) Yes, converting a multi-tape TM to single-tape only increases the amount of space used by a constant factor. PSPACE = ?SPACE(??) polynomial space NPSPACE = ?NSPACE(??) nondeterministic polynomial space Check-in 17.1 2
Relationships between Time and SPACE Complexity Theorem: For ? ? ? 1) TIME ? ? 2) SPACE ? ? = ?TIME ?? ? Proof: 1) A TM that runs in ?(?) steps cannot use more than ?(?) tape cells. 2) A TM that uses ?(?) tape cells cannot use more than ?? ? time without repeating a configuration and looping (for some ?). SPACE ? ? TIME 2? ? ? Corollary: P PSPACE Theorem: NP PSPACE [next slide] 3
NP PSPACE Theorem: NP PSPACE Proof: 1. ??? PSPACE 2. If ? P? and ? PSPACE then ? PSPACE PSPACE Defn: coNP = ? ? NP} ??????? coNP ????????? = coNP NP ? all assignments satisfy ?} coNP coNP PSPACE (because PSPACE = coPSPACE) Or possibly: P P = PSPACE ? Not known. P = NP = coNP = PSPACE 4
Example: ???? Defn: A quantified Boolean formula (QBF) is a Boolean formula with leading exists ( ?) and for all ( ?) quantifiers. All variables must lie within the scope of a quantifier. A QBF is TRUE or FALSE. Check-in 17.2 How is ??? a special case of ????? (a) Remove all quantifiers. (b) Add and quantifiers. (c) Add only quantifiers. (d) Add only quantifiers. Examples: ?1= ? ? ?2= ? ? ? ? ? ? TRUE ? ? ? ? FALSE Defn: ???? = ? ? is a QBF that is TRUE} Thus ?1 ???? and ?2 ????. Theorem: ???? PSPACE 5 Check-in 17.2
???? PSPACE Theorem: ???? PSPACE Proof: On input ? 1. If ? has no quantifiers, then ? has no variables so either ? = True or ? = False. Output accordingly. 2. If ? = ? ? then evaluate ? with ? = TRUE and ? = FALSE recursively. Accept if either accepts. Reject if not. 3. If ? = ? ? then evaluate ? with ? = TRUE and ? = FALSE recursively. Accept if both accept. Rejectif not. Space analysis: Each recursive level uses constant space (to record the ? value). The recursion depth is the number of quantifiers, at most ? = | ? |. So ???? SPACE(?) 6
Example: Ladder Problem A ladder is a sequence of strings of a common length where consecutive strings differ in a single symbol. WORK PORK PORT SORT SOOT SLOT PLOT PLOY PLAY PLAY A word ladder for English is a ladder of English words. Let ? be a language. A ladder in ? is a ladder of strings in ?. Defn: ??????DFA= a ladder ?1,?2, ,?? where ?1= ? and ??= ?}. ?,?,? ? is a DFA and ?(?) contains Theorem: ??????DFA NPSPACE 7
??????DFA NPSPACE Theorem: ??????DFA NPSPACE Proof idea: Nondeterministically guess the sequence from ? to ?. Careful- (a) cannot store sequence, (b) must terminate. Proof: On input ?,?,? 1. Let ? = ? and let ? = |?|. 2. Repeat at most ? times where ? = ?. 3. Nondeterministically change one symbol in ?. 4. Reject if ? ?(?). 5. Accept if ? = ?. 6. Reject [exceeded ? steps]. WORK PORK PORT SORT SOOT SLOT PLOT PLOY PLAY ? Space used is for storing ? and ?. ??????DFA NSPACE(?). ? ? ? ? ? ?(?) Theorem: ??????DFA PSPACE (!) 8
??????DFA PSPACE Theorem: ??????DFA SPACE(?2) Proof: Write ? Here s a recursive procedure to solve the bounded DFA ladder problem: ? ? if there s a ladder from ? to ? of length ?. ? ? by a ladder in ?(?)} ???????-??????DFA= ?,?,?,? ? a DFA and ? ?-? = On input ?,?,?,? Let ? = ? = |?|. 1. For ? = 1, accept if ?,? ?(?) and differ in 1 place, else reject. 2. For ? > 1, repeat for each ? of length |?| ?/2? and ? 4. Accept both accept. 5. Reject [if all fail]. WORK ? 2 recurse Check-in 17.3 ?/2? [division rounds up] 3. Recursively test ? Find an English word ladder connecting MUST and VOTE. (a) Already did it. (b) I will. ? AAAA AAAB AAAC AAAD AAAZ AABA AABB ABLE Test ?,?,? ??????DFA with ?-? procedure on input ?,?,?,? for ? = ? ? 2 recurse Space analysis: Each recursive level uses space ? ? (to record ?). Recursion depth is log? = ? ? = ?(?). Total space used is ?(?2). PLAY 9 Check-in 17.3
Quick review of today 1. Space complexity 2. SPACE ? ? , NSPACE ? ? 3. PSPACE, NPSPACE 4. Relationship with TIME classes 5. ???? PSPACE 6. ??????DFA NSPACE(?) 7. ??????DFA SPACE(?2) 10
MIT OpenCourseWare https://ocw.mit.edu 18.404J Theory of Computation Fall 2020 For information about citing these materials or our Terms of Use, visit: https://ocw.mit.edu/terms.
