0
$\begingroup$

Title says it all. I am curious of the 3SAT problem but limited to instances where only one clause is left unsatisfied by any literal assignment.

Do such problems exist, and if they do, what is it known which complexity class these instances / this sub-problem belong to?

Improve this question
$\endgroup$
6
  • $\begingroup$ Can you describe the motivation? One trivial example is $(x \lor x \lor x) \land (\bar x \lor \bar x \lor \bar x)$. $\endgroup$
    – Dmitry
    Oct 4, 2022 at 23:33
  • 1
    $\begingroup$ By the probabilistic argument, you can show that each such instance has at most $8$ non-trivial (i.e. not always true) clauses. $\endgroup$
    – Dmitry
    Oct 5, 2022 at 0:55
  • $\begingroup$ This is a question of pure intellectual curiosity born out of having far too much time on my hands lately. I have no specific application. I have an intuition that such problems must be somehow easier, but am having trouble showing that the general 3SAT can be reduced to ^ and otherwise determining a simple means of solving such cases. $\endgroup$
    – gdoug
    Oct 5, 2022 at 18:25
  • $\begingroup$ @Dmitry do you mind providing any resources on this probabilistic argument? $\endgroup$
    – gdoug
    Oct 5, 2022 at 18:28
  • 2
    $\begingroup$ It’s a simple observation. The probability that a random assignment falsifies a given 3-clause is 1/8 (or more, if you allow repeated literals), and by assumption, these events (for the clauses in your instance) are pairwise disjoint, hence there cannot be more than 8 of them. $\endgroup$
    – Emil Jeřábek
    Oct 6, 2022 at 8:23

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.

Browse other questions tagged or ask your own question.