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?
  • $\begingroup$ relevant?: wisdom.weizmann.ac.il/~oded/PS/CC/l11.ps $\endgroup$ Oct 17 '12 at 0:44
  • $\begingroup$ 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 $\endgroup$
    – AJed
    Oct 17 '12 at 1:59
  • $\begingroup$ 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$"? $\endgroup$
    – A.Schulz
    Oct 17 '12 at 7:09
  • $\begingroup$ This questions is stated unclearly, so I am downvoting on it. $\endgroup$ 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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