0
$\begingroup$

What is the complexity class of the problem if there exist two different interpretations that do not satisfy a given Boolean formula? I believe the problem of existence of an interpretation that does not satisfy a given Boolean formula is in P

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ Please edit your question to explain what an interpretation is. $\endgroup$
    – Kyle Jones
    Jun 13 at 17:16
  • $\begingroup$ Please specify the problem more clearly. Formally, what is the language (the decision problem)? Informally, a way to state it is to describe the inputs to the algorithm, and the desired output. How is the Boolean formula represented? CNF? DNF? Arbitrary logical formula? What's the context where you encountered this or the motivation? What are your thoughts on this question? $\endgroup$
    – D.W. ♦
    Jun 14 at 8:04

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.