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?

$\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 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 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 at 18:25
  • $\begingroup$ @Dmitry do you mind providing any resources on this probabilistic argument? $\endgroup$
    – gdoug
    Oct 5 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$ Oct 6 at 8:23

0

Your Answer

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

Browse other questions tagged or ask your own question.