# Given a truth table, force a contradiction

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?
-
relevant?: wisdom.weizmann.ac.il/~oded/PS/CC/l11.ps – Sasho Nikolov Oct 17 '12 at 0:44
Are you sure it is defined as you did. Given your example, wouldnt be more logical if you had the result of x1 ^ x2 but the witness did not ? Therefore, you are asking the witness to give you x1, x2 - and if the result of one of x1 ^ x2 contradict what you already have, then the witness is lying ? -- that is, you want to a combination of x1 and x2 that give you what you already know from x1 ^ x2 ? --- in such case, isn't the problem a satisfiability problem ? - I m just looking for more details – AJed Oct 17 '12 at 1:59
I like the problem, but it still a bit unclear for me. Can you give a formula with winning strategy and one without. Also what do you mean with "I have to prove some formula $F$"? – A.Schulz Oct 17 '12 at 7:09
This questions is stated unclearly, so I am downvoting on it. – Andrej Bauer Dec 28 '12 at 8:41

It appears the question that you are asking is:

What is the set of formula for which a witness attempting to prove the formula false will always fail?

That is, you are asking whether a formula is valid: whether it is true for every interpretation. A formula is valid if and only if its negation is unsatisfiable, which according to this resource is Co-NP complete.

-