CS 1510 Reductions and NP-hardness Homework Problems1. (2 points) A square matrix M is lower triangular if each entry above the main diagonal is zero, thatis, each entry Mi,j, with i < j, is equal to zero. Show that if there is an O(n2) time algorithm formultiplying two n by n lower triangular matrices then there is an O(n2) time algorithm for multiplyingtwo arbitrary n by n matrices.2. (2 points) Show that if there is an O(nk), k ≥ 2, time algorithm for inverting a nonsingular n by nmatrix C then there is an O(nk) time algorithm for multiply two arbitrary n by n matrices A and B.For a square matrix A, A inverse, denoted A−1, is the unique matrix such that AA−1= I, where I isthe identity matrix with 1’s on the main diagonal and 0’s everyplace else. Note that not every squarematix has an inverse, e.g. the all zero matrix.HINT: If you want to multiply n by n matrices A and B, consider the 3n×3n matrix C of the followingform:I A 00 I B0 0 IWhere I is the n × n identity matrix.3. (4 points) Show that if there is an O(nk), k ≥ 1, time algorithm for squaring a degree n polynomial,then there is an O(nk) time algorithm for multiplying two degree n polynomials. Assume that thepolynomials are given by their coefficients. Assume that all coefficients you compute can be fit intoone word of computer memory.4. (2 points) Consider the following variant of the minimum Steiner tree problem. The input is n pointsin the plane. Each point is given by its Cartesian coordinates. The problem is build a collection ofroads between these points so that you can reach any city from any other city and the total lengthof the roads is minimized. The collection of roads should be output as an adjacency list structure,that is, for each point p of intersection of roads there are a list of roads that meet that point. Roadsmust terminate when they meet one of the original input points, or when they meet another road. Forexample, if the points are (1, 1), (−1, 1), (1, −1), (−1, −1), (2, 2) the output would be:From the point (0, 0) there are roads to the points (1, 1), (−1, 1), (1, −1), and (−1, −1). From the point(1, 1) there are roads to (0, 0) and (2, 2). From the point (−1, 1) there is a road to (0, 0). From thepoint (1, −1) there is a road to (0, 0). From the point (−1, −1) there is a road to (0, 0).Roads from (1, 1) to (−1, −1), and from (1, −1) to (−1, 1) would not be allowed because they cross. Aroad from (−1, −1) to (2, 2) would not be allowed since it would cross the point (1, 1).Show by reduction that if you can solve this problem in linear time, then you can sort n numbers inlinear time.5. (6 points) Show that if one of the following three problems has a polynomial time algorithm then theyall do.• The problem is to determine whether a Boolean Circuit (with gates NOT, binary AND, andbinary OR) has some input that causes all of the output lines to be 1. Assume that the fan-out(the number of gates that the output of a single gate can be fed into) of the gates in a circuit maybe arbitrary.• The problem is to determine whether a Boolean Circuit (with gates NOT, arbitrary fan-in AND,and arbitrary fan-in OR), has some input that causes all of the output lines to be 1. Assume thatthe fan-out (the number of gates that the output of a single gate can be fed into) of the gates ina circuit may be arbitrary.• Determine whether a Boolean formula, with NOT, binary AND, and binary OR operations, issatisfiable.Make sure to state what reductions you show, even if some of the reductions are trivial.HINT: You need to show how to simulate unbounded fan-in AND and OR gates with bounded fan-inAND and OR gates. You need to show how to transform a Boolean formula into a circuit. And youneed to show how to transform a circuit into a Boolean Formula (this is probably the trickiest partdue to the unbounded fan-out).6. (6 points) Show that if one of the following three problems has a polynomial time algorithm then theyall do.• The input is two undirected graphs G and H. The problem is to determine if the graphs areisomorphic.• The input is two directed graphs G and H. The problem is to determine if the graphs areisomorphic.• The input is two undirected graphs G and H, and an integer k. The problem is to determine ifthe graphs are isomorphic and all the vertices in each graph have degree k.Intuitively, two graphs are isomorphic if on can name/label the vertices so that the graphs are identical.More formally, two undirected graphs G and H are isomorphic if there is a bijection f from the verticesof G to the vertices of H such that (v, w) is an edge in G if and only if (f(v), f(w)) is an edge in H.More formally, two directed graphs G and H are isomorphic if there is a bijection f from the verticesof G to the vertices of H such that (v, w) is a directed edge in G if and only if (f(v), f(w)) is a directededge in H. The degree of a vertex is the number of edges incident to that vertex.NOTE: There is no known polynomial time algorithm for the graph isomorphism problem. For reasonsthat are too complicated to go into here, it is unlikely that the graph isomorphism problem is NP-hard(but there is no known proof of this).HINT: It is straight-forward to solve undirected graph isomorphism using a routine for directed graphisomorphism. The other direction is not so straight-forward. Your reductions here probably shouldintroduce some additional pieces to the graphs so the only possible isomorphisms are of the type thatyou seek in the original problem.7. (2 points) Show that the subset sum problem is self-reducible. The decision problem is to take acollection of positive integers x1, . . . , xnand an integer L and decide if there is a subset of the xi’s thatsum to L. The optimization problem asks you to return the actual subset if it exits. So you must showthat if the decision problem has a polynomial time algorithm then the optimization problem also hasa polynomial time algorithm.8. (2 points) The input to the Hamiltonian Cycle Problem is an undirected graph G. The problem isto find a Hamiltonian cycle, if one exists. A Hamiltonian cycle is a simple cycle that spans G. Showthat the Hamiltonian cycle problem is self reducible. That it, show that if there is a polynomial timealgorithm that determines whether a graph has a Hamiltonian cycle, then there is a polynomial timealgorithm to find Hamiltonian cycles.9. (2 points) Show that the clique problem is self-reducible. The