Suggested languages for you:

Americas

Europe

Problem 12

Describe the error in the following fallacious "proof" that $\mathrm{P} \neq \mathrm{NP}\(. Assume that \)\mathrm{P}=\mathrm{NP}$ and obtain a contradiction. If \(\mathrm{P}=\mathrm{NP}\), then \(S A T \in \mathrm{P}\) and so for some \(k\), \(S A T \in T I M E\left(n^{k}\right)\). Because every language in NP is polynomial time reducible to \(S A T\), you have NP $\subseteq \operatorname{TIME}\left(n^{k}\right) .\( Therefore, \)\mathrm{P} \subseteq \operatorname{TIME}\left(n^{k}\right) .$ But by the time hierarchy theorem, \(\operatorname{TIME}\left(n^{k+1}\right)\) contains a language that isn't in \(\operatorname{TIME}\left(n^{k}\right)\), which contradicts $\mathrm{P} \subseteq \operatorname{TIME}\left(n^{k}\right)\(. Therefore, \)\mathrm{P} \neq \mathrm{NP}$.

Expert verified

The error in the fallacious "proof" is the incorrect implication that NP ⊆ TIME(n^k) because SAT ∈ TIME(n^k). If P = NP, it means that there exists a polynomial-time algorithm for each problem in NP, not necessarily within a specific n^k complexity. Also, the "proof" misuses the Time Hierarchy Theorem to reach a contradiction, which does not hold. Consequently, this "proof" does not prove that P ≠ 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 9

(a) Let \(A\) be any language and \(k \in \mathcal{N}\). If \(A \in \mathrm{P}\), then \(\operatorname{pad}\left(A, n^{k}\right) \in \mathrm{P}\) because you can determine whether \(w \in p a d\left(A, n^{k}\right)\) by writing \(w\) as $s \\#^{l}\( where \)s$ doesn't contain the # symbol, then testing whether \(|w|=|s|^{k}\); and finally testing whether \(s \in A\). Implementing the first test in polynomial time is straightforward. The second test runs in time poly \((|s|)\), and because \(|s| \leq|w|\), the test runs in time poly \((|w|)\) and hence is in polynomial time. If $\operatorname{pad}\left(A, n^{k}\right) \in \mathrm{P}\(, then \)A \in \mathrm{P}\( because you can determine whether \)w \in A\( by padding \)w\( with # symbols until it has length \)|w|^{k}$ and then testing whether the result is in \(\operatorname{pad}\left(A, n^{k}\right)\). Both of these actions require only polynomial time. (b) Assume that \(\mathrm{P}=\operatorname{SPACE}(n)\). Let \(A\) be a language in \(\operatorname{SPACE}\left(n^{2}\right)\) but not in \(\operatorname{SPACE}(n)\) as shown to exist in the space hierarchy theorem. The language \(\operatorname{pad}\left(A, n^{2}\right) \in \operatorname{SPACE}(n)\) because you have enough space to run the \(O\left(n^{2}\right)\) space algorithm for \(A\), using space that is linear in the padded language. Because of the assumption, \(p a d\left(A, n^{2}\right) \in \mathrm{P}\), hence $A \in \mathrm{P}\( by part (a), and hence \)A \in \operatorname{SPACE}(n)$, due to the assumption once again. But that is a contradiction.

Chapter 9

Prove that if NEXPTIME \(\neq\) EXPTIME, then \(P \neq N P\). You may find the function pad, defined in Problem \(9.13\), to be helpful.

Chapter 9

Define the unique-sat problem to be \(U S A T=\\{\langle\phi\rangle \mid \phi\) is a Boolean formula that has a single satisfying assignment \(\\}\). Show that \(U S A T \in \mathrm{P}^{S A T}\).

Chapter 9

The containment TIME $\left(2^{n}\right) \subseteq \operatorname{TIME}\left(2^{2 n}\right)\( holds because \)2^{n} \leq 2^{2 n}$. The containment is proper by virtue of the time hierarchy theorem. The function \(2^{2 n}\) is time constructible because a TM can write the number 1 followed by \(2 n\) os in \(O\left(2^{2 n}\right)\) time. Hence the theorem guarantees that a language \(A\) exists that can be decided in $O\left(2^{2 n}\right)\( time but not in \)o\left(2^{2 n} / \log 2^{2 n}\right)=o\left(2^{2 n} / 2 n\right)\( time. Therefore, \)A \in \operatorname{TIME}\left(2^{2 n}\right)\( but \)A \notin \operatorname{TIME}\left(2^{n}\right) .$

Chapter 9

Give a circuit that computes the parity function on three input variables and show how it computes on input \(011 .\)

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