Complexity Theory Insights

CMSC 28100 Introduction to Complexity Theory Complexity Theory Spring 2025 Instructor: William Hoza 1

Sublinear-space computation 1 1 1 0 Read-only input tape 1 1 0 0 # $ Read-write work tape 2

The complexity class L L is the set of languages that can be decided using ? log? cells of the work tape 3

EXP PSPACE NP P L 4

Nondeterministic log space computation We define NL to be the class of languages that can be decided by a nondeterministic log-space Turing machine Equivalently: NL is the class of languages for which membership can be verified in logarithmic space with the extra requirement that the verifier can only read the certificate one time from left to right 5

The ?-? connectivity problem STCONN = { ?,?,? ? is a digraph, ? and ? are vertices, and there is a directed path from ? to ?} Claim:STCONN NL Proof sketch: Take a nondeterministic walk through ? starting from ? for ? steps. If we ever reach ?, accept; otherwise, reject. Verifier perspective: Certificate = path from ? to ? 6

Two surprises about NL We expect that P NP. However, in the space complexity world Savitch s Theorem: NL SPACE log2? We expect that NP coNP. However, in the space complexity world Immerman-Szelepcs nyi Theorem: NL = coNL 7

Proof of Savitchs theorem Savitch s Theorem: NL SPACE log2? Proof step 1: Show that STCONN SPACE log2? Proof step 2: Show that STCONNis NL-complete 8

Savitchs algorithm Claim (Savitch s algorithm): STCONN SPACE log2? Proof sketch: Let s figure out: is there a path from ? to ? of length at most 2?? 1. For all ? ?: Recursively figure out whether there is a path from ? to ? of length at most 2? 1 a) Recursively figure out whether there is a path from ? to ? of length at most 2? 1 b) c) If both such paths exist, halt and accept 2. Halt and reject Space complexity is ? ?log? , which is ? log2? when ? = log ? 9

Proof of Savitchs theorem Savitch s Theorem: NL SPACE log2? Proof step 1: Show that STCONN SPACE log2? Proof step 2: Show that STCONN is NL-complete 10

Log-space reductions To prove Savitch s theorem, we will use a new type of reduction Let ?1,?2 0,1 Definition: We write ?1 L?2 if there exists : 0,1 0,1 such that For every ? ?1, we have ? ?2 ( YES maps to YES ) For every ? ?1, we have (?) ?2 ( NO maps to NO ) can be computed in ?(log?) space Definition on next slides 11

Space-bounded transducer 1 1 1 0 Read-only input tape 1 $ 1 # Read-write work tape 1 1 1 1 0 0 Write-only output tape 12

Space complexity for string-valued functions Let : 0,1 0,1 and let ?: Def: We say is computable in ? ? space if there is a 3-tape TM ? such that: If we initialize ? with ? on tape 1, then it halts with ? on tape 3 ? never modifies tape 1 and ? s behavior does not depend on what it reads on tape 3 The tape 1 head is always located within one cell of the input When the input has length ?, the tape 2 head visits ? ? ? cells 13

NL-completeness Let ? 0,1 Definition: We say that ? is NL-complete if ? NL and for every ? NL, we have ? L? 14

STCONN is NL-complete Theorem: STCONN is NL-complete Proof: We have already shown STCONN NL Now let ? be a nondeterministic log-space TM that decides ? Reduction: ? = ?,?,? Each vertex in ?represents a configuration of ? on ?, namely, the internal state, the contents of the work tape, and the locations of heads 15

STCONN is NL-complete We put an edge from ? to ? if ? can go from ? to ? in a single step (with ? written on input tape) We let ? = the initial configuration and ? = the accepting configuration (Without loss of generality, the accepting configuration is unique) YES maps to YES NO maps to NO Exercise: The reduction can be computed in ? log? space 16

Proof of Savitchs theorem Savitch s Theorem: NL SPACE log2? Proof step 1: Show that STCONN SPACE log2? Proof step 2: Show that STCONN is NL-complete Proof step 3: Show that SPACE log2? is closed under log-space mapping reductions 17

Composing space-bounded algorithms Let ?: 0,1 0,1 be a function computable in space ? ?? where ??: Let ?: 0,1 0,1 be a function computable in space ? ?? where ??: Assume ?? is monotone increasing and ??? log? Define ? = max ? 0,1?? ? Lemma: ? ? is computable in space ? ??? + ?? ? 18

Composing space-bounded algorithms Lemma: ? ? is computable in space ? ??? + ?? ? Let ??, ?? be the TMs that compute ?,?. Our job is to simulate ?? on ? ? Key challenge: We cannot afford to write ? ? down! We remember the location of ?? s input-tape head, ?, in our work space To simulate a single step of ??, first we need to compute ? ?? To compute it, we simulate ?? on ? and discard all but ?-th output symbol! 19

Composing space-bounded algorithms Lemma: ? ? is computable in space ? ??? + ?? ? How much space did we use? ?? ? space used by simulated ?? ??? space used by simulated ?? ? log ? space to keep track of the location of ?? s input-tape head and ?? s output-tape head 20

Closure under reductions Corollary: Let ?1,?2 0,1 . If ?1 L?2 and ?2 SPACE log2? , then ?1 SPACE log2? Proof: The log-space reduction runs in polynomial time (cf. L P) Therefore, ? poly |?| By the lemma, ?1 SPACE log? + log2poly ? = SPACE log2? 21

Proof of Savitchs theorem Savitch s Theorem: NL SPACE log2? Proof step 1: Show that STCONN SPACE log2? Proof step 2: Show that STCONN is NL-complete Proof step 3: Show that SPACE log2? is closed under log-space mapping reductions 22