(Note: For Dr. Tate’s section only) Consider the following instance of the Post Correspondence Problem (PCP): \[ \left\{ \left[ {\texttt{ba}}\over{\texttt{ac}} \right] , \left[ {\texttt{ba}}\over{\texttt{bba}} \right] , \left[ {\texttt{abc}}\over{\texttt{ab}} \right] , \left[ {\texttt{a}}\over{\texttt{cab}} \right] , \left[ {\texttt{cab}}\over{\texttt{a}} \right] , \left[ {\texttt{abc}}\over{\texttt{ac}} \right] \right\} \]
Find a match.
Prove that a match is impossible if the \(\left[{\texttt{ba}}\over{\texttt{ac}} \right]\) tile is removed.
Given what you did above, the following statement is obviously incorrect: “Since the PCP is undecidable, if you are given a set of PCP tiles you cannot decide whether a match is possible or not.” Explain why this is not correct, and how you can modify the general statement so that it is a true statement of what the undecidability of the PCP implies.
Theorem 5.2 on pages 217–218 showed that \(E_{TM}\) is undecidable. Unlike many of the other reductions in Section 5.1, this one can not be turned into a mapping reduction – the discussion in Example 5.27 explains why not. However, the idea used in the proof of Theorem 5.2 can be used to create a mapping reduction for related languages. For this problem, let \[ {ALL}_{TM} = \{ \langle M\rangle\,|\, M \text{ is a TM and } L(M)=\Sigma^* \}, \] and prove \({ALL}_{TM}\) is undecidable by creating a mapping reduction \(A_{TM}\leq_{m}{ALL}_{TM}\) based on the ideas of the Theorem 5.2 proof (other than writing it as a mapping reduction, there are only two minor changes that need to be made!).
Here is a simple (and incorrect!) “proof” that \(A_{DFA}\) is undecidable (recall that \(A_{DFA}\) was defined on page 194 and Theorem 4.1 shows that it is decidable): Given input \(\langle B,w\rangle\) for \(A_{DFA}\), we convert \(B\) in to a TM \(M\) by replacing the DFA transition function with a TM transition function that never changes anything on the tape and always moves right. It’s easy to see that \(\langle M,w\rangle\in A_{TM}\) if and only if \(\langle B,w\rangle\in A_{DFA}\). Therefore \(A_{TM}\leq_{m} A_{DFA}\) and so \(A_{DFA}\) is undecidable.
What is the flaw in this “proof”?
Prove that \(P\) is closed under complement.
Prove that \(NP\) is closed under union.
The problem \(LPATH\) is defined in Problem 7.21 in the textbook.
Prove that \(LPATH\) is NP-complete.
If we fix one of the variables, then the problem can be solved in polynomial time. In particular, we fix \(k\) to be \(4\) and define
\[ 4PATH = \{\langle G,a,b\rangle\,|\,G \text{ contains a simple path of length at least 4 from } a \text{ to } b\} .\]
Prove that \(4PATH\) is in \(P\).
Investigate online (do not use AI!) what the consequences would be if \(P\) vs \(NP\) were solved. Write three paragraphs: One focused on what are some possible consequences if \(P=NP\), one focused on what are some consequences of \(P\neq NP\), and a concluding paragraph where you indicate which you think is true, and which you wish were true (these don’t have to be the same!). Cite your sources.