P, NP-Completeness Exercises

Problem 1: The Class P (35 points) §

1. (25) Show that the class $P$ is closed under union, intersection, concatenation and complement.

Answer: §

Success

Union §

Let $L_1$ and $L_2$ be two languages in P. These languages are decidable and may be decided by algorithms $A_1$ and $A_2$. We can construct a new algorithm $A$ which decides the union of $L_1$ and $L_2$. M = “On input x:

1. Run $A_1$ on input x.
2. Run $A_2$ on input x.
3. If either A1 or A2 accept x, then A accepts x.

The running time of A is the sum of the running times of A1 and A2. These algorithms would be polynomial-time. Thus, the union of $L_1$ and $L_2$ is in P.

Intersection §

Similarly to union, if we have two languages $L_1$ and $L_2$ in P we may construct a new algorithm A that decides the union of $L_1$ and $L_2$ with corresponding algorithms $A_1$ and $A_2$. M = “On input x:

1. Run $A_1$ on input x.
2. Run $A_2$ on input x.
3. If either A1 or A2 accept x, then A accepts x.

Like before, the running time of A is the sum of the running times of A1 and A2. These algorithms would be polynomial-time. Thus, the intersection of $L_1$ and $L_2$ is in P.

Concatenation: §

If we have $L_1$ and $L_2$ we may construct a new language $L_3=L_1{L}_2$. $L_3$ consists of all strings which can be split into two parts with part one in $L_1$ and part two in $L_2$. We may construct an algorithm on $L_1$ & $L_2$ to determine if they are in $L_3$: M = “On string input x:

1. Run $L_1$ on input x to check if the first slice of the string is in $L_1$.
2. Run $L_2$ on input x to check if the second slice of the string is in $L_2$.
3. If the above conditions are both met, we accept x, otherwise reject x.

Because the potential number of splits is linear, we may perform these checks in polynomial-time the overall runtime is polynomial. Thus, the concatenation of $L_1$ and $L_2$ is in P

Complement §

If we have language $L_1$ in P we may construct a new language $L_2$ which is the complement of $L_1$. We can construct an algorithm to decide whether string x is in L2: M = “On string input x:

1. Run $L_1$ on input x to check if x is NOT in L1.
2. If x is NOT in $L_1$, accept, otherwise reject.

This algorithm runs in polynomial-time and as such the complement of $L_1$ is in P.

1. (10) Show that $E{Q}_{DFA}$ is in the class $P$.

Answer: §

Success

To demonstrate that $E{Q}_{DFA}$ is in $P$, we can construct a polynomial-time algorithm to solve the decision problem.

This may be done by constructing the symmetric difference automaton C from two DFAs A and B. DFA C accepts a string only if exactly one of A or B accept it. This is done in polynomial time.

Additionally, we will construct an algorithm which decides whether a language L(C) is empty or not in polynomial time.

Consider a Turing Machine M: M = “On input C which is a DFA:

1. Mark the start state of C.
2. Move along the transition into the next unmarked state and mark it.
3. Repeat step 2 until there is no remaining and reachable unmarked states.
4. If there is a path from the start state to any accept state, we accept. Otherwise reject.

The above algorithm effectively is a graph search algorithm which runs in polynomial time.

As both algorithms run in polynomial time, their sums also run in polynomial time. This shows that $E{Q}_{DFA}$ is in P.

2. (10) $AL{L}_{DFA}$ = { < D > | D is a DFA with L(D) = Σ* }. Show that $AL{L}_{DFA}$ is in the class $P$.

Answer: §

Success

We need to show that there is a polynomial time algorithm to decide if a given DFA $D$ recognizes every string over its alphabet, this is to say if $L(D)={\Sigma }^{\ast }$.

The following is a polynomial-time algorithm which solve this decision problem:

1. Identify all the accept states in $D$. This can be done in linear time given the size of the DFA.

2. Perform a graph search algorithm starting from the start state of $D$. Mark every state that can be reached from the start state. This can also be done in linear time given the size of the DFA.

3. Check if all states marked in step 2 are accepting states. If they are, then $D$ accepts all possible strings. If there remains any state that is reachable from the start state and is not an accept state, then $L(D)\ne {\Sigma }^{\ast }$.

This algorithm may be performed in polynomial time. This shows that $AL{L}_{DFA}$ is in $P$.

Problem 2: The Class NP (25 points) §

1. (10) Show that the class NP is closed under union and concatenation.

Answer: §

Success

If we have two languages $L_1$ and $L_2$ that are in NP, we can construct two machines $M_1$ and $M_2$ to decide $L(M_1)$ and $L(M_2)$ in NP time.

$M_{UNION}$ = On input <$M_1$, $M_2$, s>:

1. Run $M_1$ on $M_2$ or $M_2$ on s: this must be chosen nondeterministically.
2. If it accepts, accept. Otherwise, reject.

The Nondeterministic Turing Machine (NTM) $M_{UNION}$ runs in polynomial time if the NTMs for $L_1$ and $L_2$ both run in polynomial time, which is the case because $L_1$ and $L_2$ are in NP. Therefore, $L_1\cup L_2$ is also in NP.

$M_{CONCATENATION}$ = On input <$M_1$, $M_2$, s>:

1. Choose a point to split the input string so that xy = s: the position to split must be chosen nondeterministically.
2. Run $M_1$ on x.
3. Run $M_2$ on y.
4. If both instructions accept, we accept. Otherwise, we reject.

The NTM $M_{CONCATENATION}$ runs in polynomial time if the NTMs for $L_1$ and $L_2$ both run in polynomial time, which is the case because $L_1$ and $L_2$ are in NP. Therefore, $L_1{L}_2$ is also in NP.

This shows the class NP is closed under union and concatenation.

2. (15) We say that graphs $G$ and $H$ are isomorphic if the nodes of $G$ may be reordered so that it is identical to $H$. Let $ISO=\{⟨G,H⟩|G\text{ and }H$ are isomorphic graphs }.  Show that $ISO$ is in the class $NP$.

Answer: §

Success

Let certificate C (sequence of nodes representing a path from $s$ to $t$ in graph $G$) be the reordering of G’s nodes: M = On input <G,H,C>:

1. Check that C is a valid reordering of G’s nodes with no repetitions.
2. Let $G_C$ be the reordered G.
3. If $G_C=H$, accept, otherwise reject.

All steps within this algorithm take either polynomial or linear time. This shows that ISO is in the class NP.

Problem 3: NP-Completeness (25 points) §

A subset $S$ of the nodes of a graph $G$ is a dominating set if every other node of $G$ is adjacent to some node in $S$. Consider the language:

$\text{DOMINATING-SET}=\{⟨G,k⟩|G$ has a dominating set with $k$ nodes }

Show that $DOMINATING-SET$ is NP-complete by reduction from $VERTEX-COVER$.

Answer: §

Success

We can show that DOMINATING-SET is NP-complete by creation a function to convert input for VERTEX-COVER into input for DOMINATING-SET.

M = On input <G,k>:

1. Create graph H.
2. For each non-zero vertex in G, add a vertex v to H.
3. For each edge e = (u,v) in G:
4. Add a vertex w to H.
5. Add edges (u,v,), (u,w), and (v,w) to H.
6. Output <H,K>

Our graph G has a vertex cover iff H has a dominating set. If $G^{\prime }$ has a vertex cover $C$ of size $k^{\prime }$, then $C$ is also a dominating set in $G$ of size $k$. This is because for each node $w$ that we added in $G$, it is connected to nodes $u$ and $v$ in $G^{\prime }$ which are in the vertex cover $C$ (by definition of vertex cover), and hence $w$ is dominated by $C$.

• If $G$ has a dominating set $D$ of size $k$, then $D$ is also a vertex cover in $G^{\prime }$ of size $k^{\prime }$. This is because $D$ cannot contain any new nodes we added in $G$ (since these nodes are not connected to each other, they cannot dominate each other). Hence $D$ must be a subset of the original nodes from $G^{\prime }$, and since $D$ is a dominating set in $G$, it must be a vertex cover in $G^{\prime }$.

This reduction can be done in polynomial time, because we can iterate through all the edges in $G^{\prime }$ and add new nodes in $G$ in polynomial time.

Therefore, $DOMINATING-SET$ is NP-complete.

Problem 4: NP-not-so-Completeness (30 points) §

You can find the $SUBSET-SUM$ problem in our slides, and the proof of its NP-completeness in chapter 7.  Let $UNARY-SSUM$ be $SUBSET-SUM$ except with all numbers represented in unary.

1. (15) Why is $UNARY-SSUM$ not NP-complete when $SUBSET-SUM$ is?

Answer: §

Success

UNARY-SSUM is not NP-complete because of its input encoding. Due to the nature of unary notation, input size grows linearly with the numeric value that the unary input represents. This may throw off arithmetic calculuations. This is dissimilar to SUBSET-SUM which is in binary notation and has logarithmic representation size for a number.

2. (15) Show that $UNARY-SSUM$ is in the class P.

Answer: §

Success

We will show that $UNARY-SSUM$ is in $P$ by providing a polynomial-time algorithm that solves this decision problem.

1. Let $U$ be the sum that we’re trying to achieve, and let the set $u_1,u_2,...,u_n$ represent our unary numbers. Initialize an array $dp$ of size $U+1$, where $dp[i]$ will be true if there’s a subset that adds up to $i$ and false otherwise.

2. Set $dp[0]$ to be true, because there’s the empty subset which always sums up to 0.

3. For each $u_i$ from $1$ to $n$, and for each $j$ from $U$ decremented to $u_i$, set $dp[j]$ to be true if $dp[j-u_i]$ is true. This means that if there’s a subset that sums up to $j-u_i$, then by adding $u_i$ to that subset, we can also sum up to $j$.

4. Finally, if $dp[U]$ is true, then there’s a subset that sums up to $U$, so we accept. Otherwise, we reject.

The runtime of this algorithm is $O(nU)$, where $n$ is the number of unary numbers and $U$ is the sum we are trying to achieve. The size of a unary number is proportional to the value of the number and as such we may determine that the runtime is polynomial with respect to the size of the input. This shows that $UNARY-SSUM$ is in P.

Problem 5: A Contrasting Path (35 points) §

A simple path in a graph is a path that contains no repeated vertices, and (therefore) no cycles. Let G be an undirected graph and consider the languages:

$SPATH=\{⟨G,a,b,k⟩|G\text{ has a simple path of length }\le k\text{ from a to b}\}$

$LPATH=\{⟨G,a,b,k⟩|G\text{ has a simple path of length }\ge k\text{ from a to b }\}$

1. (10) Show that SPATH is in the class P.

Answer: §

Success

SPATH is in the class P since there is a polynomial time algorithm to decide if a given undirected graph $G$ has a simple path of length $\le k$ from $a$ to $b$.

This may be solved as follows:

1. Use the Breadth-First Search (BFS) algorithm from vertex $a$ in the graph $G$. BFS visits vertices in increasing order of their distance from $a$, this means once we reach vertex $b$, we have found a shortest path from $a$ to $b$.

2. If BFS reaches the vertex $b$ and the length of the path found is $\le k$, accept. If BFS has searched all vertices reachable from $a$ without finding $b$ or if the length of the path found from $a$ to $b$ is $>k$, reject.

Since BFS runs in linear-time with respect to the number of edges and vertices of the graph ($O(|V|+|E|)$ where $|V|$ is the the number of vertices and $|E|$ are the number of edges, it is a polynomial-time algorithm. This shows that $SPATH$ is in $P$.

3. (25) Show that LPATH is NP-complete.

Answer: §

Success

We will show that $LPATH$ is NP-complete by demonstrating that it is in NP and that it is NP-hard.

$LPATH$ is in NP: Given a sequence of nodes representing a path from $s$ to $t$ in graph $G$, we can verify in polynomial time whether the path has no repeated nodes and whether it has length at least $k$. We can do this by checking each consecutive pair of nodes in the sequence to ensure that they form an edge in $G$ and storing a set of nodes we have visited to ensure that no node appears more than once in the sequence. This shows that $LPATH$ is in NP.

Now to prove that LPATH is NP-hard by reducing from the Hamiltonian Path problem, which is known to be NP-complete:
Given an instance $⟨G^{\prime },s^{\prime },t^{\prime }⟩$ of $HP$, we can construct an instance $⟨G,s,t,k⟩$ of $LPATH$ where $G=G^{\prime }$, $s=s^{\prime }$, $t=t^{\prime }$, and $k$ is the number of nodes in $G^{\prime }-1$.

$⟨G^{\prime },s^{\prime },t^{\prime }⟩$ is in $HP$ iff $⟨G,s,t,k⟩$ is in $LPATH$. A Hamiltonian path in $G^{\prime }$ from $s^{\prime }$ to $t^{\prime }$ is a simple path that visits every node exactly once, so its length is the number of nodes in $G^{\prime }$ - 1, = $k$. As $k$ is the number of nodes in $G$ minus 1, if there is a simple path of length $k$ from $s$ to $t$ in $G$, this path must be a Hamiltonian path from $s^{\prime }$ to $t^{\prime }$ in $G^{\prime }$.

This reduction can be done in polynomial time, because we can count the number of nodes in $G^{\prime }$ in polynomial time.

Therefore, $LPATH$ is NP-hard.

==This shows that $LPATH$ is NP-complete.==

#evergreen