Suppose I have a formula, and a lying witness is attempting to make it evaluate to False.
Given a truth table $c(F_1,…, F_n)$, how could you force a lying witness to contradict herself?
A contradiction is simply when the witness's statements are logically impossible; i.e. that $x_1,x_2$ are each True, but $x_1 \space AND\space x_2$ is False.
- How can I characterize the set of all formula for which I force the witness to contradict herself?
- What complexity class does this problem fall in?