Suggested languages for you:

Americas

Europe

Problem 12

Call graphs \(G\) and \(H\) isomorphic if the nodes of \(G\) may be reordered so that it is identical to \(H .\) Let \(I S O=\\{\langle G, H\rangle \mid G\) and \(H\) are isomorphic graphs \(\\} .\) Show that \(I S O \in \mathrm{NP}\).

Expert verified

To show that ISO ∈ NP, we provide a non-deterministic polynomial-time algorithm that verifies whether a given pair of graphs is isomorphic or not. The algorithm uses a certificate, which is a permutation vector representing a bijection between the vertex sets of two graphs. It then verifies if the bijection preserves adjacency by checking all pairs of vertices for adjacency in both graphs. The complexity of this algorithm is O(n^2), which is polynomial in both the size of the certificate and the size of the graphs, so ISO ∈ NP.

What do you think about this solution?

We value your feedback to improve our textbook solutions.

- Access over 3 million high quality textbook solutions
- Access our popular flashcard, quiz, mock-exam and notes features
- Access our smart AI features to upgrade your learning

Chapter 7

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

Chapter 7

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 \(\mathrm{P}=\mathrm{NP}\) assumption implies that \(S A T\) is in \(\mathrm{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.)

Chapter 7

Consider the algorithm MINIMIZE, which takes a DFA \(M\) as input and outputs \(\mathrm{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]=\\{r \in Q \mid\) no edge joins \(q\) and \(r\) in \(G\\} .\) 8\. Form a new DFA $M^{\prime}=\left(Q^{\prime}, \Sigma, \delta^{\prime}, q_{0}^{\prime}, A^{\prime}\right)$ where \(Q^{\prime}=\\{[q] \mid q \in Q\\}\) (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}=\\{[q] \mid q \in A\\} .\) 9\. Output \(\left\langle M^{\prime}\right\rangle . "\) a. Show that \(M\) and \(M^{\prime}\) are equivalent. b. Show that \(M^{\prime}\) is minimal-that is, no DFA with fewer states recognizes the same language. You may use the result of Problem \(1.52\) without proof. c. Show that MINIMIZE operates in polynomial time.

Chapter 7

Call a regular expression star-free if it does not contain any star operations. Then, let $E Q_{\mathrm{SF}-\mathrm{REX}}=\\{\langle R, S\rangle \mid R\( and \)S\( are equivalent star-free regular expressions \)\\}$. Show that \(E Q_{\mathrm{SF}-\mathrm{REX}}\) is in coNP. Why does your argument fail for general regular expressions?

Chapter 7

Let \(C N F_{\mathrm{H}}=\\{\langle\phi\rangle \mid \phi\) is a satisfiable cnf- formula where each clause contains any number of literals, but at most one negated literal \(\\} .\) Show that \(C N F_{\mathrm{H}} \in \mathrm{P} .\)

The first learning app that truly has everything you need to ace your exams in one place.

- Flashcards & Quizzes
- AI Study Assistant
- Smart Note-Taking
- Mock-Exams
- Study Planner