6. Conceptually, NP represents the class of decision problems whose yes answers can be ver- ified...

Transcribed Image Text:

6. Conceptually, NP represents the class of decision problems whose "yes" answers can be ver- ified efficiently. In this problem, we will consider its counterpart: coNP {L | LЄ NP}, representing the class of decision problems whose "no" answers are efficiently verifiable. (a) Show that NP coNP 0. (b) Optional bonus. Consider the following language: = SMALLER FACTOR = {(x, y): x has a factor, z, such that 1 < z < y}. Show that SMALLER FACTOR Є CONP. Hint: You can assume that it is possible to verify if a given number is prime in polynomial time. 6. Conceptually, NP represents the class of decision problems whose "yes" answers can be ver- ified efficiently. In this problem, we will consider its counterpart: coNP {L | LЄ NP}, representing the class of decision problems whose "no" answers are efficiently verifiable. (a) Show that NP coNP 0. (b) Optional bonus. Consider the following language: = SMALLER FACTOR = {(x, y): x has a factor, z, such that 1 < z < y}. Show that SMALLER FACTOR Є CONP. Hint: You can assume that it is possible to verify if a given number is prime in polynomial time.

Answer rating: 100% (QA)

a We must prove that there is a problem in NP that is not in coNP in order to establish that NP coNP The Subset Sum issue is among them Subset Sum Is ... View the full answer