# 3SAT instances where no assignment fails to satisfy more than one clause: do they eixst, and what complexity class do they belong in?

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?

• Can you describe the motivation? One trivial example is $(x \lor x \lor x) \land (\bar x \lor \bar x \lor \bar x)$. Oct 4, 2022 at 23:33
• By the probabilistic argument, you can show that each such instance has at most $8$ non-trivial (i.e. not always true) clauses. Oct 5, 2022 at 0:55
• 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. Oct 5, 2022 at 18:25
• @Dmitry do you mind providing any resources on this probabilistic argument? Oct 5, 2022 at 18:28
• 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. Oct 6, 2022 at 8:23