Let's say we have a friend Bob.
Bob is blue, he's had a nasty run in with a can of paint.
Now let's assume that Bob has a Boolean formula,
not necessarily this one but just some Boolean formula.
And suppose Bob comes to us and tells us I've already
found out that this Boolean formula is satisfiable.
Now let's say we don't necessarily trust Bob.
Bob is given to exaggeration.
We'd like to be able to figure out in polynomial time
whether or not Bob is telling us the truth.
So how would be go about doing that?
Let's say Bob came to us with a complete series of snapshots
from a nondeterministic RAM solving SAT on his formula.
Would that be enough for us to believe that he had a satisfiable formula?
How about if he had a list of satisfiable clauses?
For example, he had a list that had x as the satisfiable clause
and not Y as a satisfiable clause.
Then for the entire Boolean formula,
could we then determine whether it was satisfiable or not?
What about if you had a satisfying assignment for all
of the variables in the formula?
What if we had all the calls to if_better on the Boolean formula?
So not necessarily a complete series of snapshots
from a nondeterministic RAM solving SAT on his formula,
but just all the calls to if_better.
Would that be enough for us to believe Bob?
And finally, what if we had a satisfying assignment
for not all the variables but 90% of the variables in Bob's formula.
Could we believe him then?
Please check all that apply.