Suggested languages for you:

Americas

Europe

Problem 20

Prove that an oracle \(C\) exists for which $\mathrm{NP}^{C} \neq \operatorname{coNP}^{C} .$

Expert verified

Using the diagonalization technique, we define a language \(L\), and we show that for any oracle \(C\), either \(L\in\mathrm{NP}^C\) or \(L\in\mathrm{coNP}^C\), but not both. By constructing an oracle Turing machine \(A\) with access to an oracle \(C = \mathrm{NP}^{C} \oplus \mathrm{coNP}^{C}\), we argue that if \(L \in \mathrm{NP}^{A}\), it implies \(L \in \mathrm{NP}^{C}\), and if \(L \in \operatorname{coNP}^{A}\), it implies \(L \in \mathrm{coNP}^{C}\). Since both can't be true simultaneously, there must exist an oracle \(C\) such that \(\mathrm{NP}^{C} \neq \operatorname{coNP}^{C}\), completing the proof.

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

Prove that TIME $\left(2^{n}\right) \subsetneq \operatorname{TIME}\left(2^{2 n}\right)$.

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

Give regular expressions with exponentiation that generate the following languages over the alphabet \(\\{0,1\\}\). A. All strings of length 500 \({ }^{A} \mathrm{~b} .\) All strings of length 500 or less A. All strings of length 500 or more A d. All strings of length different than 500 e. All strings that contain exactly \(5001 \mathrm{~s}\) f. All strings that contain at least 500 is g. All strings that contain at most 500 is h. All strings of length 500 or more that contain a 0 in the 500 th position i. All strings that contain two os that have at least 500 symbols between them

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