=========================================================================== CSC 363H Lecture Summary for Week 11 Fall 2007 =========================================================================== ----------------- Self-reducibility ----------------- Example 3: VERTEX-COVER-SEARCH Input: Graph G, integer k. Output: A vertex cover of size k, if one exists (None otherwise). - Idea 2: Check if G-v contains a VC of size (k-1). - Algorithm: VCS(G,k): if not VC(G,k): return None C = {} # the vertices in a vertex cover of G for each vertex v in V, and while k > 0: if VC(G-v, k-1): C = C U {v}; G = G - v; k = k - 1 return C - Correctness: Loop invariant: G contains a VC of size k. At each iteration, . if G-v contains a VC of size k-1 (C), then G contains a VC of size k that includes v (C U {v}); . if G contains a VC of size k that includes v (C), then G-v contains a VC of size k-1 (C - {v}) -- so by contrapositive: if G-v does not contain a VC of size k-1, then v does not belong to any VC of size k in G). - Runtime: O((n+1)*t(n,m) + n*(n+m)) -- for each vertex v, we perform one call to VC in time t(n,m) and compute G-v in time O(n+m). Optimization problems: - Some search problems with one or more numerical parameters naturally occur in practice in the form of optimization problems, e.g., . MAX-CLIQUE . MIN-VERTEX-COVER . etc. As in the case of vertex cover above, optimization problem can also be self-reducible by using decision problem algorithm to find optimal value of relevant parameter(s). Example: MAX-CLIQUE Idea: Given G, perform binary search in range [1,n] by making calls to CL(G,k) for various values of k, in order to find maximum value k such that G contains a k-clique but no (k+1)-clique. Then, use search algorithm to find k-clique. (Note: Linear search for value of k would also be OK because search is in the range [1,n] and input size = n.) Similar idea would work for MIN-VERTEX-COVER. ---------------- Space Complexity ---------------- SPACE(s(n)) = { L : L is a language that can be decided by a TM running in worst-case space O(s(n)), i.e., the TM never uses more than O(s(n)) tape cells on any input } NSPACE(s(n)) = { L : L is a language that can be decided by a NTM running in worst-case space O(s(n)), i.e., the NTM never uses more than O(s(n)) tape cells on any input } Fact: If language L is recognized by a TM M running in space O(s(n)), then L is decidable. Proof: Main idea: The only way that M can loop is by repeating a configuration exactly (because it is limited in how many cells it can use). We can simulate M until it stops or repeats a configuration, thereby deciding L(M). Details: Since M uses <= c*s(n) tape cells on any input, there are at most m^{c*s(n)} possible tape contents that M can enter during its computation (where m = number of symbols in tape alphabet) -- m symbols per cell for c*s(n) cells. For each possible tape content, there are c*s(n) positions that M's head can be in, and k = |Q| different states that M can be in. So M can run through at most k*c*s(n)*m^{c*s(n)} many different configurations before it enters some configuration twice (meaning M is in an infinite loop). Since k, c, m are constants with respect to the input size, this means it is possible to decide L(M) by simulating M and rejecting if M ever runs for more than k*c*s(n)*m^{c*s(n)} = 2^{O(s(n))} steps. This shows SPACE(s(n)) subset of TIME(2^O(s(n)))! Unlike time, space much less affected by details of model (e.g., using k tapes saves time but not space -- information must still be stored). Surprising result: SAT in SPACE(n) -- keep track of original formula, truth-value assignment to its variables, and simplified formula, all in linear space; simply evaluate formula on each possible truth-value assignment, reusing space. So space seems more "powerful" than time. Intuition: space can be reused; time cannot. Surprising result (Savitch's Theorem): NSPACE(s(n)) subset of SPACE((s(n))^2). Proof idea: NTM running in space O(s(n)) runs in nondeterministic time 2^O(s(n)). Trying out all computation branches takes too much space. Instead, use algorithm to test whether NTM can get from initial configuration to accepting configuration by recursively breaking up computation in two halves -- doing this properly (see textbook) gets space usage down to O((s(n))^2): O(s(n)) for storing configurations, and log(2^O(s(n))) = O(s(n)) for recursion depth. --------- Polyspace --------- PSPACE = U_{k >= 0} SPACE(n^k) = { all languages decided in polyspace } By Savitch's Theorem, NPSPACE = PSPACE. Clearly, P subset PSPACE and NP subset NPSPACE, so P subset NP subset NPSPACE = PSPACE. What about coNP? coNP subset coNPSPACE = coPSPACE = PSPACE (deterministic polyspace decider for L yields deterministic polyspace decider for ~L by simply swapping accept/reject). Even more so than with NP, it seems "clear" that P =/= PSPACE (think of linear-space algorithm for SAT). However, question still open! Given we can't prove P =/= PSPACE, what to do? Same as for NP: identify "hardest" problems in PSPACE. Language A is PSPACE-complete if: - A in PSPACE. - A is PSPACE-hard: B <=p A for all B in PSPACE. Notice we still use polytime reductions (<=p), because we're concerned with P vs PSPACE so we need notion of reduction no stronger than smallest class of interest, to ensure if B <=p A and A in P, then B in P. Examples: - Quantified boolean formula = propositional formula with quantifiers on propositional variables, e.g., \-/ p -] q ( ((p \/ q) -> r) /\ (~p -> (q /\ r)) ). Fully quantified boolean formula = all variables quantified and all quantifiers at the front ("prenex normal form"). Fully quantified boolean formulas are always either true or false. Note: asking "is propositional formula F satisfiable" same as asking "is -] p_1 -] p_2 ... -] p_k F true" (where p_1,p_2,...,p_k are all variables of F). TQBF = { fully quantified boolean formulas that are true } TQBF in PSPACE: On input F: - If F has no quantifiers, then evaluate F and accept iff it is true. - If F = -] x F', then recursively evaluate F'[x=0] and F'[x=1] and accept iff either computation accepts. (using "-]" to represent existential quantifier) - If F = \-/ x F', then recursively evaluate F'[x=0] and F'[x=1] and accept iff both computations accept. (using "\-/" to represent universal quantifier) Recursion depth = number of variables of F and each level stores values of formula for one variable, so total space used for recursion is linear. Evaluating F at each level also requires linear space, but this can be shared between calls. TQBF is PSPACE-hard: For any language A in PSPACE, construct a quantified formula that represents the computation of a PSPACE TM for A. Details are in the textbook. - Many types of two-player games for which we can ask: given a certain game configuration, does player 1 have a guaranteed win? For example, "Generalized Geography": on directed graph G, player I picks start node, then players take turns moving along edges, without ever going back to previously visited nodes. Last player to move wins. GG = { : G is a directed graph, b is a node in G, and player I has a winning strategy playing generalized geography from start node b, i.e., there are moves for player I to win no matter how player II moves } GG in PSPACE: On input : - Reject if no outgoing edge from b. - Otherwise, remove b and all its edges to get G_1; let b_1, ..., b_k be endpoints of edges from b. - Recursively run on inputs , ..., ; reject if all accept (player II wins); accept if one rejects. Recursion depth = number of nodes in G (linear). Information stored at each call = nodes b_1, ..., b_k; since each node stored at most once overall, total information stored is linear. GG is PSPACE-hard: TQBF <=p GG: see construction in textbook. Even more so than NP-complete problems, PSPACE-complete problems have no time-efficient solutions. However, they still have efficient solutions in memory usage, and their time complexity has not been proven outside P. So are there any decidable languages we can _prove_ outside P?