Conceptually, NP represents the class of decision problems whose "yes" instances can be efficiently verified (without incorrectly accepting any "no" instances). In this problem, you will consider its counterpart coNP = {L : L NP}. This represents the set of decision problems whose "no" instances can be efficiently verified (because the "no" instances of L are exactly the "yes" instances of L). Ultimately, you will show that proving NP 6= coNP would resolve the P vs. NP problem. (a) Consider the language TAUT = { : is a tautology}, i.e., the set of Boolean formulas that are satisfied by every assignment. Show that TAUT coNP. (b) It is currently unknown whether coNP = NP (though they are widely believed to be unequal). For example, TAUT is in coNP but is not known (or believed) to be in NP. Let V be some efficient verifier for TAUT. Explain why the following V 0 is not necessarily an efficient verifier for TAUT, and thereby fails to establish that TAUT NP. 1: function V 0 (, c) 2: return the opposite of what V (, c) returns (c) We can analogously define coP = {L : L P}

Answer rating: 100% (QA)

a To show that TAUT is in coNP we need to prove that the complement of TAUT is in NP The complement ... View the full answer