The decision problem \(\textsf{CLIQUE}=\{\langle G,k\rangle\,:\,G\) is a graph containing a clique of size \(k\}\) is defined on page 1087, along with a discussion of the clique problem. Show how to create a polynomial time algorithm to find the largest clique in a graph (in other words, output the actual subset of vertices in the largest clique) if \(\textsf{CLIQUE}\in P\).
People who are interested in solving optimization problems would really like it if P=NP, with someone discovering an efficient algorithm for some NP-complete problem. All sorts of problems could be solved and optimized if this were this case! However, cryptographers really, really hope that P≠NP. Let’s see why.
First some brief background: Encryption takes a secret message \(m\) (called the plaintext) and an encryption key, and turns that into unintelligible data \(c\) (called the ciphertext). The receiver of the ciphertext uses a decryption function \(D\) along with decryption key \(k\) to recover the plaintext, so \(D(k,c)=m\). In one style of attack, called a “known-plaintext attack,” the attacker knows a matching pair of plaintext/ciphertext values \((m,c)\), and also knows the decryption algorithm \(D\), but does not know the key that will decrypt \(c\) to \(m\). The goal of the attacker is to compute \(k\) from this captured data, so that they can decrypt other captured ciphertext values for which they don’t know the secret plaintext.
For the rest of this problem, we are only looking at one decryption algorithm \(D\), which can be computed in polynomial time, and both the key and the ciphertext inputs are \(n\)-bit binary strings. Note that in practice, \(n\) varies from 128 bits to 4096 bits, depending on the algorithm.
Consider decision problem \(\textsf{KEY-PREFIX}=\{\langle m,c,x\rangle\,:\,x\) is a prefix of an \(n\)-bit string \(k\) such that \(m=D(k,c)\}\). (\(x\) being a prefix of \(k\) means that if \(k\) is \(n\) bits long and \(x\) is \(|x|\leq n\) bits long, then the first \(|x|\) bits of \(k\) are \(x\).) Prove that \(\textsf{KEY-PREFIX}\in NP\).
Prove that if \(\textsf{KEY-PREFIX}\in P\), then there is a polynomial time algorithm that takes a matching plaintext/ciphertext pair \((m,c)\) and computes a key \(k\) such that \(D(k,c)=m\).
Explain clearly what this means for the complexity of known-plaintext attacks if P=NP (your explanation should be general – think beyond this specific function \(D\) and to the general case of cryptography as a whole).
So that you’re not left with the impression that secure cryptography is impossible if P=NP, consider the following situation, which is compatible with the above arguments even if P=NP: Encrypting and decrypting operations take \(10\cdot n^2\) nanoseconds, testing \(\textsf{KEY-PREFIX}\) takes \(100\cdot n^3\) nanoseconds, and so computing the key using this procedure takes \(100\cdot n^4\) nanoseconds. If \(n=10,000\), how long would it take to encrypt and decrypt? How long would it take to compute the key (to break the code)? If you had a particularly high-security application, you might consider using \(n=100,000\). Repeat your calculations for this value of \(n\).
Consider \(\textsf{HALF-HAMILTONIAN}=\{\langle G\rangle\,:\,G=(V,E)\) is an undirected graph with a simple cycle through \(|V|/2\) vertices\(\}\). Prove that \(\textsf{HALF-HAMILTONIAN}\) is NP-complete.
While the minimum spanning tree problem has efficient algorithms, some other spanning tree problems are much harder. Recall the generic definition of a spanning tree: Given a connected graph \(G=(V,E)\), a spanning tree is a subset of edges \(E'\subseteq E\) such that \(G'=(V,E')\) is connected and acyclic. Define a a special type of spanning tree, a “\(k\)-spanner” (for \(k\geq 2\)) of a connected graph \(G=(V,E)\), as a spanning tree \(E'\subseteq E\) such that every vertex in \(G'=(V,E')\) has degree \(k\) or less.
All connected graphs have a spanning tree, but not all graphs have \(k\)-spanners for various values of \(k\). Give an example of a connected graph that does not have a 3-spanner. (Hint: This is possible with 5 vertices.)
Define \(\textsf{K-SPANNER}=\{\langle G,k\rangle\,:\, G\) is a connected graph and has a \(k\)-spanner\(\}\). Prove that \(\textsf{K-SPANNER}\) is NP-complete. (Hint: You may take as a “known NP-complete problem” any of the problems proved NP-complete in Section 34.5, and any of the ones mentioned as NP-complete in the exercises at the end of that section.)
This problem remains NP-complete for any fixed constant \(k\). Define \(\textsf{4-SPANNER}=\{\langle G\rangle\,:\, G\) is a connected graph and has a \(4\)-spanner\(\}\). Prove that \(\textsf{4-SPANNER}\) is NP-complete. (Hint: If you’re clever, you can solve parts b and c together!)