CS151 Complexity Theory Lecture 4 April 12, 2019 A puzzle A puzzle: two kinds of trees dept hn

... ... cover up nodes with c colors promise: never color arrow same as blank determine which kind of tree in poly(n, c) steps? April 12, 2019 A puzzle

dept hn ... April 12, 2019 ... A puzzle dept

hn ... April 12, 2019 ... Introduction Ideas depth-first-search; stop if see how many times may we see a given arrow

color? at most n+1 pruning rule? if see a color > n+1 times, it cant be an arrow node; prune # nodes visited before know answer? at most c(n+2) April 12, 2019 Sparse languages and NP We often say NP-compete languages are hard

More accurate: NP-complete languages are expressive lots of languages reduce to them April 12, 2019 Sparse languages and NP Sparse language: one that contains at most poly(n) strings of length n not very expressive can we show this cannot be NP-complete (assuming P NP) ? yes: Mahaney 82 (homework problem)

Unary language: subset of 1* (at most n strings of length n) April 12, 2019 Sparse languages and NP Theorem (Berman 78): if a unary language is NP-complete then P = NP. Proof: let U 1* be a unary language and assume SAT U via reduction R (x1,x2,,xn) instance of SAT

April 12, 2019 Sparse languages and NP self-reduction tree for : (xx1,x2,,xn) (x0,x2,,xn) (x1,x2,,xn) . . .

(x0,0,,0) ... (x1,1,,1) satisfying assignment April 12, 2019 Sparse languages and NP applying reduction R: R(x(xx1,x2,,xn))

R(x(x0,x2,,xn)) R(x(x1,x2,,xn)) . . . R(x(x0,0,,0)) ... R(x(x1,1,,1))

satisfying assignment April 12, 2019 Sparse languages and NP on input of length m = |(x(x1,x2,,xn)|(x, R produces string of length p(m) Rs different outputs are colors 1 color for strings not in 1* at most p(m) other colors puzzle solution can solve SAT in poly(p(m) +1, n+1) = poly(m) time!

April 12, 2019 Summary nondeterministic time classes: NP, coNP, NEXP NTIME Hierarchy Theorem: NP NEXP major open questions: ? P = NP

April 12, 2019 ? NP = coNP Summary NP-intermediate problems (unless P = NP) technique: delayed diagonalization unary languages not NP-complete (unless P = NP) true for sparse languages as well (homework)

complete problems: circuit SAT is NP-complete UNSAT is coNP-complete succinct circuit SAT is NEXP-complete April 12, 2019 Summary coNEXP NEXP

EXP PSPACE NP coNP P L April 12, 2019 Remainder of lecture nondeterminism applied to space reachability two surprises:

Savitchs Theorem Immerman/Szelepcsnyi Theorem April 12, 2019 Nondeterministic space NSPACE(f(n)) = languages decidable by a multi-tape NTM that touches at most f(n) squares of its work tapes along any computation path, where n is the input length, and f :N N

April 12, 2019 Nondeterministic space Robust nondeterministic space classes: NL = NSPACE(log n) NPSPACE = k NSPACE(nk) April 12, 2019 Reachability Recall: at most nk configurations of given NTM M running in NSPACE(log n).

easy to determine if C xL yields C in one step configuration graph for M on input x: q April 12, 2019 qstartx1x2x3xn

accept qreject xL qaccept qreject Reachability Conclude: NL P and NPSPACE EXP

S-T-Connectivity (STCONN): given directed graph G = (V, E) and nodes s, t, is there a path from s to t ? Theorem: STCONN is NL-complete under logspace reductions. April 12, 2019 Reachability Proof: in NL: guess path from s to t one node at a time given L NL decided by NTM M construct

configuration graph for M on input x (can be done in logspace) s = starting configuration; t = qaccept April 12, 2019 Two startling theorems Strongly believe P NP nondeterminism seems to add enormous power for space: Savitch 70: NPSPACE = PSPACE

and NL SPACE(log2n) April 12, 2019 Two startling theorems Strongly believe NP coNP seems impossible to convert existential into universal for space: Immerman/Szelepscnyi 87/88: NL = coNL April 12, 2019

Savitchs Theorem Theorem: STCONN SPACE(log2 n) Corollary: NL SPACE(log2n) Corollary: NPSPACE = PSPACE April 12, 2019 Proof of Theorem input: G = (V, E), two nodes s and t recursive algorithm: /* return true iff path from x to y of length at most 2 i */

PATH(x, y, i) if i = 0 return ( x = y or (x, y) E ) /* base case */ for z in V if PATH(x, z, i-1) and PATH(z, y, i-1) return(true); return(false); end April 12, 2019 Proof of Theorem answer to STCONN: PATH(s, t, log n) space used: (depth of recursion) x (size of stack record)

depth = log n claim stack record: (x, y, i) sufficient size O(log n) when return from PATH(a, b, i) can figure out what to do next from record (a, b, i) and previous record April 12, 2019 Nondeterministic space Robust nondeterministic space classes:

NL = NSPACE(log n) NPSPACE = k NSPACE(nk) April 12, 2019 Second startling theorem Strongly believe NP coNP seems impossible to convert existential into universal for space: Immerman/Szelepscnyi 87/88: NL = coNL

April 12, 2019 I-S Theorem Theorem: ST-NON-CONN NL Proof: slightly tricky setup: input: G = (V, E), two nodes s, t s s yes

no t April 12, 2019 t I-S Theorem want nondeterministic procedure using only O(log n) space with behavior:

s yes inpu t t qaccept qreject April 12, 2019 s no inpu t

t qaccept qreject I-S Theorem observation: given count of # nodes reachable from s, can solve problem for each v V, guess if it is reachable if yes, guess path from s to v if guess doesnt lead to v, reject. if v = t, reject. else counter++

if counter = count accept April 12, 2019 I-S Theorem every computation path has sequence of guesses only way computation path can lead to accept: correctly guessed reachable/unreachable for each node v

correctly guessed path from s to v for each reachable node v saw all reachable nodes t not among reachable nodes April 12, 2019 I-S Theorem R(i) = # nodes reachable from s in at most i steps R(0) = 1: node s we will compute R(i+1) from R(i) using O(log n) space and nondeterminism

computation paths with bad guesses all lead to reject April 12, 2019 I-S Theorem Outline: in n phases, compute R(1), R(2), R(3), R(n) only O(log n) bits of storage between phases in end, lots of computation paths that lead to reject only computation paths that survive have computed correct value of R(n)

apply observation. April 12, 2019 I-S Theorem computing R(i+1) from R(i): R(xi) = R(x2) = 6 Initialize R(i+1) = 0 For each v V, guess if v reachable from s in at most i+1 steps

April 12, 2019 I-S Theorem if yes, guess path from s to v of at most i+1 steps. Increment R(i+1) if no, visit R(i) nodes reachable in at most i steps, check that none is v or adjacent to v for u V guess if reachable in i steps; guess path to u; counter++ KEY: if counter R(i), reject at this point: can be sure v not reachable

April 12, 2019 I-S Theorem correctness of procedure: two types of errors we can make (1) might guess v is reachable in at most i+1 steps when it is not wont be able to guess path from s to v of correct length, so we will reject. easy type of error

April 12, 2019 I-S Theorem (2) might guess v is not reachable in at most i+1 steps when it is then must not see v or neighbor of v while visiting nodes reachable in i steps. but forced to visit R(i) distinct nodes therefore must try to visit node v that is not reachable in i steps wont be able to guess path from s to v of correct length, so we will reject.

April 12, 2019 easy type of error Summary nondeterministic space classes NL and NPSPACE ST-CONN NL-complete April 12, 2019

Summary Savitch: NPSPACE = PSPACE Proof: ST-CONN SPACE(log2 n) open question: NL = L? Immerman/Szelepcsnyi : NL = coNL Proof: ST-NON-CONN NL April 12, 2019 Introduction

Power from an unexpected source? we know P EXP, which implies no polytime algorithm for Succinct CVAL poly-size Boolean circuits for Succinct CVAL ?? Does NP have linear-size, log-depth Boolean circuits ?? April 12, 2019 Outline Boolean circuits and formulas uniformity and advice the NC hierarchy and parallel computation

the quest for circuit lower bounds a lower bound for formulas April 12, 2019 Boolean circuits circuit C directed acyclic graph

nodes: AND (); OR (); NOT (); variables xi x1 x2 x3 xn C computes function f:{0,1}n {0,1} in natural way

identify C with function f it computes April 12, 2019 Boolean circuits size = # gates depth = longest path from input to output formula (or expression): graph is a tree every function f:{0,1}n {0,1} computable by a circuit of size at most O(n2n) AND of n literals for each x such that f(x) = 1 OR of up to 2n such terms April 12, 2019

Circuit families circuit works for specific input length were used to f:* {0,1} circuit family : a circuit for each input length C1, C2, C3, = {Cn} {Cn} computes f iff for all x C|(xx|(x(x) = f(x) {Cn} decides L, where L is the language associated with f April 12, 2019

Connection to TMs given TM M running in time t(n) decides language L can build circuit family {Cn} that decides L size of Cn = O(t(n)2) Proof: CVAL construction Conclude: L P implies family of polynomial-size circuits that decides L April 12, 2019 Connection to TMs

other direction? A poly-size circuit family: Cn = (x1 x1) if Mn halts Cn = (x1 x1) if Mn loops decides (unary version of) HALT! oops April 12, 2019 Uniformity Strange aspect of circuit family: can encode (potentially uncomputable)

information in family specification solution: uniformity require specification is simple to compute Definition: circuit family {Cn} is logspace uniform iff TM M outputs Cn on input 1n and runs in O(log n) space April 12, 2019 Uniformity Theorem: P = languages decidable by logspace uniform, polynomial-size circuit

families {Cn}. Proof: already saw () () on input x, generate C|(xx|(x, evaluate it and accept iff output = 1 April 12, 2019