Name: Alexander Miranda
Date: November 16, 2016
Assignment: Homework 4

1) Let $X$ and $Y$ be two decision problems. Suppose we know that $X$ reduces to $Y$ in polynomial time. Which of the following can we infer? Explain

a) If $Y$ is NP-complete then so is $X$.

This is not true because $X$ could just be in NP and not necessarily NP-complete.

b) If $X$ is NP-complete then so is $Y$.

This is not true because $Y$ could be any of the classes harder than NP.

c) If $Y$ is NP-complete and $X$ is in NP then $X$ is NP-complete.

This doesn't have to be true because $X$ could just be in NP.

d) If $X$ is NP-complete and $Y$ is in NP then $Y$ is NP-complete.

This is true because $Y$ is definitely in NP and if $X$ is NP-complete then it follows that so is $Y$ because $Y$ is at least as hard as $X$.

e) $X$ and $Y$ can't both be NP-complete

This is not true because there are scenarios where they can be as shown in part d directly above.

f) If $X$ is in P, then $Y$ is in P.

This is false because $Y$ is at least as hard as $X$ it could be in NP and still satisfy the condition set.

g) If $Y$ is in P, then $X$ is in P.

This is true because there is nothing easier than P therefore if $Y$ is in P then $X$ has to also be in P.

In summary:

We can only infer d and g because $X$ reduces to $Y$ means that if you had a black box to solve $Y$ efficiently you could use it to solve $X$ efficiently. $X$ is therefore no harder than $Y$.

2) Consider the problem COMPOSITE: given an integer $y$, does $y$ have any factors other than one and itself? For this exercise, you may assume that COMPOSITE is in NP, and you will be comparing it to the well-known NP-complete problem SUBSET-SUM: given a set $S$ of $n$ integers and an integer target $t$, is there a subset of $S$ whose sum is exactly $t$? Clearly explain whether or not each of the following statements follows from that fact that COMPOSITE is in NP and SUBSET-SUM is NP-complete:

a) SUBSET-SUM $\leq_p COMPOSITE$

This statement does not hold true. The reason for this is because SUBSET-SUM is NP-complete which then allows us to reduce it to any other NP-complete problem. We do not know if COMPOSITE is also NP-complete only that it resides in NP. Knowing these things we cannot say definitively that SUBSET-SUM can be reduced to COMPOSITE.

b) If there is an $O(n^3)$ algorithm for SUBSET-SUM, then there is a polynomial time algorithm for $COMPOSITE$.

This is true because if SUBSET-SUM is in NP-complete therefore if SUBSET-SUM is solvable in polynomial time than all problems in NP-complete are solvable in polynomial time.

c) If there is a polynomial algorithm for $COMPOSITE$, then $P = NP$

This is false because we are told that $COMPOSITE$ is within NP not necessarily within NP-complete therefore if $COMPOSITE$ can be solved in polynomial time than it could be a matter of $COMPOSITE$ being misclassified like the algorithm used to find prime numbers.

d) If $P \neq NP$, then no problem in $NP$ can be solved in polynomial time.

This statement is true because it follows that if one problem in NP-complete is solvable in polynomial time than all problems in NP-complete and NP are solvable in polynomial time. The assertion stated just before is simply the negation of the statement in d.

3) Two well-known NP-complete problems are 3-SAT and TSP, the traveling salesman problem. The 2-SAT problem is a SAT variant in which each clause contains at most two literals. 2-SAT is known to have a polynomial-time algorithm. Is each of the following statements true or false? Justify your answer

a) 3-SAT $\leq_p TSP$

This statement is true because as observed in the lecture slides with the NP-completeness graph that 3-SAT can be reduced from itself to DIR-HAM-CYCLE to HAM-CYCLE to TSP. An image of the relevant slide is below:

Also both of these algorithms are NP-complete therefore they are both within NP so they can be reduced to each other so the inequality could be reversed and still be true.

b) If $P \neq NP$, then 3-SAT $\leq_p$ 2-SAT.

This statement is false because 2-SAT has a solution that runs in polynomial time and 3-SAT is NP-complete so it doesn't follow that $P \neq NP$ because 2-SAT is within $P$ so if you could reduce 3-SAT to 2-SAT it would also be in $P$ but also still be within NP-complete which causes a contradiction with $P \neq NP$.

c) If $P \neq NP$, then no NP-complete problem can be solved in polynomial time.

This statement is true because by definition of NP-complete if at least one NP-complete problem can be solved in polynomial time then it follows that all NP-complete problems can be solved in polynomial time.

4) LONG-PATH is the problem of, given $(G, u, v, k)$ where $G$ is a graph, $u$ and $v$ vertices and $k$ an integer, determining if there is a simple path in $G$ from $u$ to $v$ of length at least $k$. Show that LONG-PATH is NP-complete.

LONG-PATH is within NP since the verifying of the path is the yes-no which can be checked in polynomial time that it is a path and it is at least $k$ units long. LONG-PATH is also NP-complete because a Hamiltonian path is a special variant of LONG-PATH where we state the start, end node and $k$ equals the number of vertices in the path minus $1$.

First we show that LONG-PATH is verifiable in polynomial time. Given a sequence of vertices that make up the path we can traverse that sequence in $O(n)$ time and check the adjacency list that the next vertex is within that list, thus showing that this porition belongs in NP. The second part is to reduce an NP-complete problem to a polynomial time variant. Hamiltonian cycle detection is NP-complete. If you take the graph passed into LONG-PATH and solve it using Hamiltonian path then all that would remain would be to check every vertex that results to make sure there exists an edge to the subsequent vertex. That process can be completed in $O(V + E)$ time.

5) Graph-Coloring. Mapmakers try to use as few colors as possible when coloring countries on a map, as long as no two countries that share a border have the same color. We can model this problem with an undirected graph $G = (V,E)$ in which each vertex represents a country and vertices whose respective countries share a border are adjacent. A $k$-coloring is a function c: $V -> {1, 2, … , k}$ such that $c(u) \neq c(v)$ for every edge $(u,v) \in E$. In other words the number $1, 2, .., k$ represent the $k$ colors and adjacent vertices must have different colors. The graph-coloring problem is to determine the minimum number of colors needed to color a given graph.

a) State the graph-coloring problem as a decision problem K-COLOR. Show that your decision problem is solvable in polynomial time if and only if the graph-coloring problem is solvable in polynomial time.

The graph coloring problem can be stated as a decision problem whereby: Given a graph $G = (V,E)$ and a positive integer $k$ can the vertices of $G$ be $k$-colored such that no two adjacent vertices have the same color? The question posed is a simple yes-no. The problem can be broken into two parts, the actual graph coloring and the decision. The decision can be checked in $O(E)$ time because we would check all the edges to see if $u.color == v.color$ which can be determined in polynomial time. Therefore it follows that if graph coloring is polynomial the overall complexity will also be polynomial while if it is exponential than that will dominate thus supporting the conjecture above.

b) It has been proven that 3-COLOR is NP-complete by using a reduction from SAT. Use the fact that 3-COLOR is NP-complete to prove that 4-COLOR is NP-complete.

We can construct a graph based on the inputted graph $G$ except we add one new node that is connected with the base graph. The action/reduction of copying over all the vertices, edges and adding/connecting the new node to the others will take $O(n)$ time. We can then solve the old portion of the new graph using 3-COLOR whereby if it is possible to do then we know that the new graph with the extra node can be 4-COLOR because the new extra node can be assigned the fourth color.