Imagine that there is a large Boolean formula (not necessarily in CNF) written on the white-...

 

Transcribed Image Text:

Imagine that there is a large Boolean formula (not necessarily in CNF) written on the white- board, where n is the number of connectives (AND's, OR's, and NOT's). Perhaps n = 200. You claim that the formula is satisfiable; I claim that it is not. (a) What do you have to do to convince me that you are right? How much time (in order notation) do you need (as a function of n)? Note: Only count the time needed to actually show me that you are right, not any time needed to figure out how to do so. (b) What do I have to do to convince you that I am right? How much time (in order notation) do I need (as a function of n)? Note: Only count the time needed to actually show you that I am right, not any time needed to figure out how to do so. Imagine that there is a large Boolean formula (not necessarily in CNF) written on the white- board, where n is the number of connectives (AND's, OR's, and NOT's). Perhaps n = 200. You claim that the formula is satisfiable; I claim that it is not. (a) What do you have to do to convince me that you are right? How much time (in order notation) do you need (as a function of n)? Note: Only count the time needed to actually show me that you are right, not any time needed to figure out how to do so. (b) What do I have to do to convince you that I am right? How much time (in order notation) do I need (as a function of n)? Note: Only count the time needed to actually show you that I am right, not any time needed to figure out how to do so.