Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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?
share|improve this question
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
add comment

1 Answer

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.

share|improve this answer
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.