Assignment 6 Due: Thursday, January 23rd at start of tutorial. The following problems all concern the class NP of decision problems for which there is an easily verified certificate. 1. Give a convincing argument that every decision problem in NP is computable (even if it is not efficiently computable). 2. Can you think of a computable (decideable) decision problem which is {\em not} in the class NP? Hint: how many different certificates can there be for a given input? For both problems, the answer should be an argument that would convince anyone in the class. Each problem could be answered convincingly in about a paragraph or two. Explain any notation you use especially if it is notation not used in class.