COMS 4236: Introduction to Computational Complexity, Spring 2018 Problem Set 3, due Thursday March 8, 11:59pm on Courseworks
Please follow the homework submission guidelines posted on Courseworks.
Problem 1. [15 points]
a. Consider the following problem, called CIRCUIT-SAT-20.
Input: A Boolean circuit C with 20 input variables.
Question: Is C satisfiable, i.e. does there exist an assignment to the input variables of C for which the value of C is 1?
Show that CIRCUIT-SAT-20 is in P.
b. Suppose that A, B, C are three languages such that (1) Ap B, (2) Bp C, (3) A is
NP-complete, and (4) C is NP-complete. Show that B is also NP-complete.
Problem 2. [20 points]
a. Show that if a language L is complete for a class C under log-space or polynomial time reductions then its complement L is complete for the class coC under the same type of reductions. (Recall that coC = { L | L C }.)
b. We say that a class C is closed under a type of reductions (eg. log-space or polynomial time reductions) if, whenever L reduces to L’ and L’ is in C, then also L is in C.
Suppose that the class C is closed under a type of reductions and the language M is complete for C. Show that M is in coC if and only if C = coC.
Problem 3. [20 points]
a. Show that NP, coNP, and EXP=TIME(2nc ) are closed under polynomial time
c0
reductions.
b. Show that the class E TIME(2cn ) is not closed under polynomial time reductions.
c0
That is, there are languages L, L’ such that L p L’ and L’ E, but L E.
(Hint: Use a padding function and the time hierarchy theorem.)
Problem 4. [25 points]
a. Consider the following transformation that maps a directed graph G=(V,E) with m nodes to another directed graph G’=(V’,E’) with m2 nodes. The set of nodes of G’ is V’={ [v,i] | vV, 1≤i≤m }, and the set of edges is E’= { ([u,i],[v,i+1]) | (u,v)E, 1≤i≤m-1 } { ([v,i],[v,i+1]) | vV, 1≤i≤m-1 }.
Use this transformation to show that the Graph Reachability problem is NL-complete (under log-space reductions) even when the input is restricted to acyclic graphs and the nodes are ordered topologically.
Specifically, show that the following DAG Reachability problem is NL-complete.
Input: A directed acyclic graph H=(N,A) with set of nodes N={1,…,n} in topological order, i.e. all edges (i,j) A satisfy i <j; Two nodes s, t.
Question: Is there a path in H from s to t?
b. The Graph Cyclicity problem is as follows.
Input: A directed graph G.
Question: Does the graph contain a cycle?
Show that the Graph Cyclicity problem is NL-complete.
c. Is the Graph Acyclicity problem (Given a directed graph, is it acyclic?) NL-complete? Justify your answer.
Problem 5. [20 points]
a.Considerthefollowingsetofinequalities: ab, ac, b+ca+1, 0a.
Show that for every assignment of values 0 or 1 to b and c, there is a unique value of a over the real numbers that satisfies the inequalities, namely the value a = b c, i.e. a = 1 if both b, c are 1, and a = 0 otherwise.
b. Give a set of inequalities in variables a, b, c that has the analogous property for a=bc, i.e., for every assignment of values 0 or 1 to b and c, there is a unique real value of a that satisfies the inequalities, namely the value a=bc.
c. Show that the following “Linear Inequalities” problem is P-hard under log-space reductions. (The problem is also in P but you do not have to show this.)
Linear Inequalities:
Input: A system of linear inequalities in a set of variables.
Question: Does the system have a solution over the reals, i.e. is there an assignment of real values to the variables that satisfies all the inequalities?
(Hint: Reduce from the Circuit Value problem with fan-in 2. Introduce variables for the gates and the inputs of the circuit and include appropriate inequalities for the gates and the given input assignment to the circuit.)