Space Complexity, P vs. NP, and Savitch's Theorem in Computer Science

18.404/6.840 Lecture 18 Last time: - Space complexity - SPACE ? ? , NSPACE ? ? , PSPACE, NPSPACE - Relationship with TIME classes Today: (Sipser 8.3) - Review ??????DFA PSPACE - Savitch s Theorem: NSPACE ? ? - PSPACE-completeness - ???? is PSPACE-complete SPACE ?2? Posted: Pset 4 solutions, Pset 5

Review: 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 ?. PSPACE = NPSPACE SPACE ? ? NSPACE ? ? = {?| some 1-tape TM decides ? in space ? ? ? } = {?| some 1-tape NTM decides ? in space ? ? ? } coNP NP PSPACE = ?SPACE(??) polynomial space NPSPACE = ?NSPACE(??) nondeterministic polynomial space P Today: PSPACE = NPSPACE Or possibly: P = NP = coNP = PSPACE

Review: ??????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 ? 4 2 ? recurse AAAA AAAB AAAC AAAD AAAZ AABA AABB BOOK ? 4 ?/2? [division rounds up] 3. Recursively test ? AAAA AAAB AAAC AAAD AAAZ AABA AABB ABLE ? AAAA AAAB AAAC AAAD AAAZ AABA AABB CALL 2 recurse ? Test ?,?,? ??????DFA with ?-? procedure on input ?,?,?,? for ? = ? PLAY Space analysis: Each recursive level uses space ? ? (to record ?). Recursion depth is log? = ? ? = ?(?). Total space used is ?(?2). ? ? AAAA AAAB AAAC AAAD AAAZ AABA AABB ABLE AAAA AAAB AAAC AAAD AAAZ AABA AABB BOOK AAAA AAAB AAAC AAAD AAAZ AABA AABB CALL ? ? ? ?

PSPACE = NPSPACE SPACE ?2? Savitch s Theorem: For ? ? ?, NSPACE ? ? Proof: Convert NTM ? to equivalent TM ?, only squaring the space used. ? ??if can get from ?? to ?? in ? steps. For configurations ?? and ?? of ?, write ?? ? ??: Give recursive algorithm to test ?? ?(?) ? ??] ? = On input ??,??,? [goal is to check ?? 1. If ? = 1, check directly by using ? s program and answer accordingly. 2. If ? > 1, repeat for all configurations ?mid that use ?(?) space. ?/2 ?mid and ?mid 4. If both are true, accept. If not, continue. 5. Rejectif haven t yet accepted. ? ?0?1 ?? ? 2 ?/2 ?? 3. Recursively test ?? aaba?7da cab ? Test if ? accepts ? by testing ?start Each recursion level stores 1 config = ? ? ? space. Number of levels = log? = ? ? ? . Total ? ?2? space. ?accept where ? = number of configurations = ? ? ? ?? ? ? 2 ?accept

PSPACE-completeness Defn: ? is PSPACE-complete if 1) ? PSPACE 2) For all ? PSPACE, ? P? If ? is PSPACE-complete and ? P then P = PSPACE. PSPACE-complete Why P and not PSPACE when defining PSPACE-complete? - Reductions should be weaker than the class. Otherwise all problems in the class would be reducible to each other, and then all problems in the class would be complete. what can we conclude if ???? NP? Check all that apply. (a) P = PSPACE (b) NP = PSPACE (c) P = NP (d) NP = coNP NP-complete Check-in 18.1 Knowing that ???? is PSPACE-complete, PSPACE = NPSPACE NP P Theorem: ???? is PSPACE-complete Think of complete problems as the hardest in their associated class. Check-in 18.1

???? is PSPACE-complete Recall: ???? = ? ? is a QBF that is TRUE} Examples: ?1= ? ? ?2= ? ? ? ? ? ? ? ? ? ? ???? [TRUE] ???? [FALSE] Theorem: ???? is PSPACE-complete Proof: 1) ???? PSPACE 2) For all ? PSPACE, ? P???? Let ? PSPACE be decided by TM ? in space ??. Give a polynomial-time reduction ? mapping ? to ????. ?: QBFs ? ? = ??,? ? ? iff ??,? is TRUE Plan: Design ??,?to say ? accepts ?. ??,? simulates ? on ?.

Constructing ??,?: 1st try Tableau for ? on ? ?? Recall: A tableau for ? on ? represents a computation history for ? on ? when ? accepts ?. Rows of that tableau are configurations. ?0?1?2?3 ?? ?7?2 a ? runs in space ??, its tableau has: - ?? columns (max size of a configuration) - ??? rows (max number of steps) ?(??) Constructing ??,?. Try Cook-Levin method. Then ??,? will be as big as tableau. But that is exponential: ?? ???. Too big! ?accept

Constructing ??,?: 2nd try hide Tableau for ? on ? ? ??recursively. For configs ?? and ?? construct???, ??, ?which says ?? ???, ??, ?= ?mid ???, ?mid, ?/2 ??mid, ??, ?/2 ?? ?0?1?2?3 ?? ?7?2 a ?1,?2, ,?? as in Cook-Levin ?mid? , , ?/4 ? , , ?/4 ?mid? , , ?/4 ? , , ?/4 ?(??) Check-in 18.2 Why shouldn t we be surprised that this construction fails? (a) We can t define a QBF by using recursion. (b) It doesn t use anywhere. (c) We know that ???? P. ?mid[? , , ?/8 ] ? , , 1 defined as in Cook-Levin Size analysis: Each recursive level doubles number of QBFs. Number of levels is log??? Size is exponential. ??,?= ??start, ?accept, ? ? = ??? = ? ??. ?accept Check-in 18.2

Constructing ??,?: 3rd try ???, ??, ?= ?mid ???, ?mid, ?/2 ??mid, ??, ?/2 ??,? ??,?mid , ?mid,?? ???, ? , ?/2 (? ?) ? is equivalent to ? ? ? ? ??,?= ??start, ?accept, ? ? = ??? ? , , 1 defined as in Cook-Levin Check-in 18.3 Would this construction still work if ? were nondeterministic? (a) Yes. (b) No. Size analysis: Each recursive level adds ?(??) to the QBF. Number of levels is log??? Size is ? ?? ??= ? ?2? = ? ??. Check-in 18.3

Quick review of today 1. ??????DFA PSPACE SPACE ?2? 2. Savitch s Theorem: NSPACE ? ? 3. ???? is PSPACE-complete