Time Complexity

Answer each part TRUE or FALSE.

Answer each part TRUE or FALSE.

Which of the following pairs of numbers are relatively prime? Show the calculations that led to your conclusions.

Fill out the table described in the polynomial time algorithm for context-free language recognition from Theorem 7.16 for string $w=$ baba and CFG $G$ :

Is the following formula satisfiable?

Show that P is closed under union, concatenation, and complement.

Show that NP is closed under union and concatenation.

Let $\operatorname {CONNECTED}=\left\{ \langle G\rangle \mid G\text{ is a connected undirected graph }\right\}$. Analyze the algorithm given on page 185 to show that this language is in P.

A triangle in an undirected graph is a 3-clique. Show that TRIANGLE $\in \mathrm{P}$, where TRIANGLE $=\left\{ \langle G\rangle \mid G\text{ contains a triangle }\right\}$.

Show that $\operatorname {ALL}_{\text{DFA }}$ is in P.

In both parts, provide an analysis of the time complexity of your algorithm.

Call graphs $G$ and $H$ isomorphic if the nodes of $G$ may be reordered so that it is identical to $H$. Let $\operatorname {ISO}=\left\{ \langle G, H\rangle \mid G\text{ and }H\text{ are isomorphic graphs}\right\}$. Show that $\operatorname {ISO} \in \mathrm{NP}$.

Let

Show that $\operatorname {MODEXP} \in \mathrm{P}$. (Note that the most obvious algorithm doesn't run in polynomial time. Hint: Try it first where $b$ is a power of 2.)

A permutation on the set $\left\{ 1, \ldots , k\right\}$ is a one-to-one, onto function on this set. When $p$ is a permutation, $p^{t}$ means the composition of $p$ with itself $t$ times. Let

Show that PERM-POWER $\in \mathrm{P}$. (Note that the most obvious algorithm doesn't run within polynomial time. Hint: First try it where $t$ is a power of 2.)

Show that P is closed under the star operation. (Hint: Use dynamic programming. On input $y=y_{1} \cdots y_{n}$ for $y_{i} \in \Sigma$, build a table indicating for each $i \leq j$ whether the substring $y_{i} \cdots y_{j} \in A^{*}$ for any $A \in \mathrm{P}$.)

ᴬ Show that NP is closed under the star operation.

Let UNARY-SSUM be the subset sum problem in which all numbers are represented in unary. Why does the NP-completeness proof for SUBSET-SUM fail to show UNARY-SSUM is NP-complete? Show that UNARY-SSUM $\in \mathrm{P}$.

Show that if $\mathrm{P}=\mathrm{NP}$, then every language $A \in \mathrm{P}$, except $A=\emptyset$ and $A=\Sigma^{*}$, is NP-complete.

• Show that PRIMES $=\left\{ m \mid m\text{ is a prime number in binary }\right\} \in \mathrm{NP}$. (Hint: For $p>1$, the multiplicative group $Z_{p}^{*}=\left\{ x \mid x\text{ is relatively prime to }p\text{ and }1 \leq x<p\right\}$ is both cyclic and of order $p-1$ iff $p$ is prime. You may use this fact without justifying it. The stronger statement PRIMES $\in \mathrm{P}$ is now known to be true, but it is more difficult to prove.)

We generally believe that PATH is not NP-complete. Explain the reason behind this belief. Show that proving PATH is not NP-complete would prove $\mathrm{P} \neq \mathrm{NP}$.

Let $G$ represent an undirected graph. Also let

and

Let DOUBLE-SAT $=\left\{ \langle \phi \rangle \mid \phi \text{ has at least two satisfying assignments }\right\}$. Show that DOUBLE-SAT is NP-complete.

ᴬ Let HALF-CLIQUE $=\left\{ \langle G\rangle \mid G \text{ is an undirected graph having a complete subgraph with at least } m / 2 \text{ nodes, where } m \text{ is the number of nodes in } G\right\}$. Show that HALF-CLIQUE is NP-complete.

Let $\operatorname {CNF}_{k}=\left\{ \langle \phi \rangle \mid \phi \text{ is a satisfiable cnf-formula where each variable appears in at most }k\text{ places }\right\}$.

Let $\operatorname {CNF}_{\mathrm{H}}=\left\{ \langle \phi \rangle \mid \phi \text{ is a satisfiable cnf-formula where each clause contains any number of literals, but at most one negated literal}\right\}$. Show that $\operatorname {CNF}_{\mathrm{H}} \in \mathrm{P}$.

Let $\phi$ be a 3cnf-formula. An $\neq$-assignment to the variables of $\phi$ is one where each clause contains two literals with unequal truth values. In other words, an $\neq$-assignment satisfies $\phi$ without assigning three true literals in any clause.

A cut in an undirected graph is a separation of the vertices $V$ into two disjoint subsets $S$ and $T$. The size of a cut is the number of edges that have one endpoint in $S$ and the other in $T$. Let

Show that MAX-CUT is NP-complete. You may assume the result of Problem 7.26. (Hint: Show that $\neq S A T \leq_{\mathrm{P}}$ MAX-CUT. The variable gadget for variable $x$ is a collection of $3 c$ nodes labeled with $x$ and another $3 c$ nodes labeled with $\bar{x}$, where $c$ is the number of clauses. All nodes labeled $x$ are connected with all nodes labeled $\bar{x}$. The clause gadget is a triangle of three edges connecting three nodes labeled with the literals appearing in the clause. Do not use the same node in more than one clause gadget. Prove that this reduction works.)

You are given a box and a collection of cards as indicated in the following figure. Because of the pegs in the box and the notches in the cards, each card will fit in the box in either of two ways. Each card contains two columns of holes, some of which may not be punched out. The puzzle is solved by placing all the cards in the box so as to completely cover the bottom of the box (i.e., every hole position is blocked by at least one card that has no hole there). Let $\operatorname {PUZZLE}=\left\{ \left\langle c_{1}, \ldots , c_{k}\right\rangle \mid \text{each } c_{i} \text{ represents a card and this collection of cards has a solution}\right\}$. Show that PUZZLE is NP-complete.

A coloring of a graph is an assignment of colors to its nodes so that no two adjacent nodes are assigned the same color. Let

Show that 3COLOR is NP-complete. (Hint: Use the following three subgraphs.)

Let SET-SPLITTING $=\left\{ \langle S, C\rangle \mid S \text{ is a finite set and } C=\left\{ C_{1}, \ldots , C_{k}\right\} \text{ is a collection of subsets of } S, \text{ for some } k>0, \text{ such that elements of } S \text{ can be colored red or blue so that no } C_{i} \text{ has all its elements colored with the same color}\right\}$. Show that SET-SPLITTING is NP-complete.

Consider the following scheduling problem. You are given a list of final exams $F_{1}, \ldots , F_{k}$ to be scheduled, and a list of students $S_{1}, \ldots , S_{l}$. Each student is taking some specified subset of these exams. You must schedule these exams into slots so that no student is required to take two exams in the same slot. The problem is to determine if such a schedule exists that uses only $h$ slots. Formulate this problem as a language and show that this language is NP-complete.

This problem is inspired by the single-player game Minesweeper, generalized to an arbitrary graph. Let $G$ be an undirected graph, where each node either contains a single, hidden mine or is empty. The player chooses nodes, one by one. If the player chooses a node containing a mine, the player loses. If the player chooses an empty node, the player learns the number of neighboring nodes containing mines. (A neighboring node is one connected to the chosen node by an edge.) The player wins if and when all empty nodes have been so chosen. In the mine consistency problem, you are given a graph $G$ along with numbers labeling some of $G$ 's nodes. You must determine whether a placement of mines on the remaining nodes is possible, so that any node $v$ that is labeled $m$ has exactly $m$ neighboring nodes containing mines. Formulate this problem as a language and show that it is NP-complete.

ᴬ In the following solitaire game, you are given an $m \times m$ board. On each of its $m^{2}$ positions lies either a blue stone, a red stone, or nothing at all. You play by removing stones from the board until each column contains only stones of a single color and each row contains at least one stone. You win if you achieve this objective. Winning may or may not be possible, depending upon the initial configuration. Let SOLITAIRE $=\left\{ \langle G\rangle \mid G\text{ is a winnable game configuration }\right\}$. Prove that SOLITAIRE is NP-complete.

Recall, in our discussion of the Church-Turing thesis, that we introduced the language $D=\left\{ \langle p\rangle \mid p\text{ is a polynomial in several variables having an integral root }\right\}$. We stated, but didn't prove, that $D$ is undecidable. In this problem, you are to prove a different property of $D$-namely, that $D$ is NP-hard. A problem is NP-hard if all problems in NP are polynomial time reducible to it, even though it may not be in NP itself. So you must show that all problems in NP are polynomial time reducible to $D$.

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

Show that it is NP-complete by giving a reduction from VERTEX-COVER.

• Show that the following problem is NP-complete. You are given a set of states $Q=\left\{ q_{0}, q_{1}, \ldots , q_{l}\right\}$ and a collection of pairs $\left\{ \left(s_{1}, r_{1}\right), \ldots ,\left(s_{k}, r_{k}\right)\right\}$ where the $s_{i}$ are distinct strings over $\Sigma =\left\{ 0,1\right\}$, and the $r_{i}$ are (not necessarily distinct) members of $Q$. Determine whether a DFA $M=\left(Q, \Sigma , \delta , q_{0}, F\right)$ exists where $\delta \left(q_{0}, s_{i}\right)=r_{i}$ for each $i$. Here, $\delta (q, s)$ is the state that $M$ enters after reading $s$, starting at state $q$. (Note that $F$ is irrelevant here.)

Let $U=\left\{ \left\langle M, x, \#^{t}\right\rangle \mid \text{NTM } M \text{ accepts } x \text{ within } t \text{ steps on at least one branch}\right\}$. Note that $M$ isn't required to halt on all branches. Show that $U$ is NP-complete.

• Show that if $\mathrm{P}=\mathrm{NP}$, a polynomial time algorithm exists that produces a satisfying assignment when given a satisfiable Boolean formula. (Note: The algorithm you are asked to provide computes a function; but NP contains languages, not functions. The P = NP assumption implies that SAT is in P, so testing satisfiability is solvable in polynomial time. But the assumption doesn't say how this test is done, and the test may not reveal satisfying assignments. You must show that you can find them anyway. Hint: Use the satisfiability tester repeatedly to find the assignment bit-by-bit.)

• Show that if $\mathrm{P}=\mathrm{NP}$, you can factor integers in polynomial time. (See the note in Problem 7.38.)

ᴬ Show that if $\mathrm{P}=\mathrm{NP}$, a polynomial time algorithm exists that takes an undirected graph as input and finds a largest clique contained in that graph. (See the note in Problem 7.38.)

In the proof of the Cook-Levin theorem, a window is a $2 \times 3$ rectangle of cells. Show why the proof would have failed if we had used $2 \times 2$ windows instead.

• Consider the algorithm MINIMIZE, which takes a DFA $M$ as input and outputs DFA $M^{\prime }$. MINIMIZE = "On input $\langle M\rangle$, where $M=\left(Q, \Sigma , \delta , q_{0}, A\right)$ is a DFA:

1. Remove all states of $M$ that are unreachable from the start state. 2. Construct the following undirected graph $G$ whose nodes are the states of $M$. 3. Place an edge in $G$ connecting every accept state with every nonaccept state. Add additional edges as follows. 4. Repeat until no new edges are added to $G$ : 5. For every pair of distinct states $q$ and $r$ of $M$ and every $a \in \Sigma$ : 6. Add the edge $(q, r)$ to $G$ if $(\delta (q, a), \delta (r, a))$ is an edge of $G$. 7. For each state $q$, let $[q]$ be the collection of states $[q]=\left\{ r \in Q \mid \text{ no edge joins }q\text{ and }r\text{ in }G\right\}$. 8. Form a new DFA $M^{\prime }=\left(Q^{\prime }, \Sigma , \delta^{\prime }, q_{0}{ }^{\prime }, A^{\prime }\right)$ where $Q^{\prime }=\left\{ [q] \mid q \in Q\right\}$ (if $[q]=[r]$, only one of them is in $Q^{\prime }$ ), $\delta^{\prime }([q], a)=[\delta (q, a)]$ for every $q \in Q$ and $a \in \Sigma$, $q_{0}{ }^{\prime }=\left[q_{0}\right]$, and $A^{\prime }=\left\{ [q] \mid q \in A\right\}$. 9. Output $\left\langle M^{\prime }\right\rangle$."

For a cnf-formula $\phi$ with $m$ variables and $c$ clauses, show that you can construct in polynomial time an NFA with $O(c m)$ states that accepts all nonsatisfying assignments, represented as Boolean strings of length $m$. Conclude that $\mathrm{P} \neq \mathrm{NP}$ implies that NFAs cannot be minimized in polynomial time.

• A 2cnf-formula is an AND of clauses, where each clause is an OR of at most two literals. Let $2 S A T=\left\{ \langle \phi \rangle \mid \phi \text{ is a satisfiable 2 cnf-formula }\right\}$. Show that $2 S A T \in \mathrm{P}$.

Modify the algorithm for context-free language recognition in the proof of Theorem 7.16 to give a polynomial time algorithm that produces a parse tree for a string, given the string and a CFG, if that grammar generates the string.

Say that two Boolean formulas are equivalent if they have the same set of variables and are true on the same set of assignments to those variables (i.e., they describe the same Boolean function). A Boolean formula is minimal if no shorter Boolean formula is equivalent to it. Let MIN-FORMULA be the collection of minimal Boolean formulas. Show that if $\mathrm{P}=\mathrm{NP}$, then MIN-FORMULA $\in \mathrm{P}$.

The difference hierarchy $\mathrm{D}_{i} \mathrm{P}$ is defined recursively as

• Let MAX-CLIQUE $=\left\{ \langle G, k\rangle \mid \text{ a largest clique in }G\text{ is of size exactly }k\right\}$. Use the result of Problem 7.47 to show that MAX-CLIQUE is DP-complete.

• Let $f: \mathcal{N} \longrightarrow \mathcal{N}$ be any function where $f(n)=o(n \log n)$. Show that TIME $(f(n))$ contains only the regular languages.

• Call a regular expression star-free if it does not contain any star operations. Then, let $\operatorname {EQ}_{\text{SF-REX }}=\left\{ \langle R, S\rangle \mid R\text{ and }S\text{ are equivalent star-free regular expressions }\right\}$. Show that $\operatorname {EQ}_{\text{SF-REX }}$ is in coNP. Why does your argument fail for general regular expressions?

• This problem investigates resolution, a method for proving the unsatisfiability of cnf-formulas. Let $\phi =C_{1} \wedge C_{2} \wedge \cdots \wedge C_{m}$ be a formula in cnf, where the $C_{i}$ are its clauses. Let $\mathcal{C}=\left\{ C_{i} \mid C_{i} \text{ is a clause of } \phi \right\}$. In a resolution step, we take two clauses $C_{a}$ and $C_{b}$ in $\mathcal{C}$, which both have some variable $x$ occurring positively in one of the clauses and negatively in the other. Thus, $C_{a}=\left(x \vee y_{1} \vee y_{2} \vee \cdots \vee y_{k}\right)$ and $C_{b}=\left(\bar{x} \vee z_{1} \vee z_{2} \vee \cdots \vee z_{l}\right)$, where the $y_{i}$ and $z_{i}$ are literals. We form the new clause $\left(y_{1} \vee y_{2} \vee \cdots \vee y_{k} \vee z_{1} \vee z_{2} \vee \cdots \vee z_{l}\right)$ and remove repeated literals. Add this new clause to $\mathcal{C}$. Repeat the resolution steps until no additional clauses can be obtained. If the empty clause ( ) is in $\mathcal{C}$, then declare $\phi$ unsatisfiable. Say that resolution is sound if it never declares satisfiable formulas to be unsatisfiable. Say that resolution is complete if all unsatisfiable formulas are declared to be unsatisfiable.

• Show that P is closed under homomorphism iff $\mathrm{P}=\mathrm{NP}$.

• Let $A \subseteq 1^{*}$ be any unary language. Show that if $A$ is NP-complete, then $\mathrm{P}=\mathrm{NP}$. (Hint: Consider a polynomial time reduction $f$ from SAT to $A$. For a formula $\phi$, let $\phi_{0100}$ be the reduced formula where variables $x_{1}, x_{2}, x_{3}$, and $x_{4}$ in $\phi$ are set to the values $0,1,0$, and 0, respectively. What happens when you apply $f$ to all of these exponentially many reduced formulas?)

In a directed graph, the indegree of a node is the number of incoming edges and the outdegree is the number of outgoing edges. Show that the following problem is NP-complete. Given an undirected graph $G$ and a designated subset $C$ of $G$ 's nodes, is it possible to convert $G$ to a directed graph by assigning directions to each of its edges so that every node in $C$ has indegree 0 or outdegree 0, and every other node in $G$ has indegree at least 1?