$25$ points. L$0402$b asked you to consider the problem AlISAT$($Formula$),$ defined as follows. Formula is a positive instance of AllSAT iff it is a propositional logic statement evaluating to True regardless of what Boolean values are assigned to its variables. For example, $\text{'}(P$ OR notP $)$ AND $(Q$ OR notQ $\text{'}$ is a positive instance of AlISAT, and $\text{'}(P$ OR $Q)$ AND $(notPORnotQ)\text{'}$ is a negative instance. Note well, Formula is one particular statement, not a set of statements.

a A working verifier $V_1$ for AlISAT could take as a hint a semi$-$colon delimited list of the sets of all possible variable assignments for Formula, and return 'correct' iff Formula evaluated to True for each set of assignments. For example, if $P$ and $Q$ were the variables in Formula, then the hint would be $({?}^{\text{'}}P=$ False, $Q=$ False; $P=$ False, $Q=$ True; $P=$ True, $Q=$ False; $P=$ True, $Q=$ True' $).$ Does the existence of $V_1$ prove that AllSAT $in$ NP$?$ Explain.

$1.$b NoSAT is similar to AlISAT, but its verifier $V_2$ would return 'correct' if none of the sets of variable assignments in the hint made Formula True. Does the existence of $V_2$ prove that NoSAT $in$ NP$?$ Explain.

$1.$c Do you think SAT$($Formula$){?}_p$ NoSAT$($Formula$\text{'})?$ That is$,$ would solving NoSAT provide a way to tell if there was some way to satisfy Formula? Explain.

$1.$d Suppose that it were true that SAT$($Formula$){?}_p$ NoSAT$($Formula$\text{'}).$ Would that prove that NoSAT $lon$ NP$-$complete? Explain.

$1.$e Do you think All Af SAT$($Formula$){?}_p$ SAT$($Formula$\text{'})?$ That is$,$ would solving SAT provide a way to tell if were true that thece was nowayte satisfy Formula? Explain.

is always satis fiable