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

  • 1
    $\begingroup$ Please edit your question to explain what an interpretation is. $\endgroup$
    – Kyle Jones
    Jun 13, 2023 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, 2023 at 8:04


Your Answer

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