<p>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.</p>
<p>Do such problems exist, and if they do, what is it known which complexity class these instances / this sub-problem belong to?</p>

CC BY-SA 4.0
2022-10-04T23:33:51.890Z
Can you describe the motivation? One trivial example is $(x \lor x \lor x) \land (\bar x \lor \bar x \lor \bar x)$.
Dmitry
CC BY-SA 4.0
2022-10-05T00:55:17.730Z
By the probabilistic argument, you can show that each such instance has at most $8$ non-trivial (i.e. not always true) clauses.
Dmitry
CC BY-SA 4.0
2022-10-05T18:25:18.197Z
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.
gdoug
CC BY-SA 4.0
2022-10-05T18:28:03.760Z
@Dmitry do you mind providing any resources on this probabilistic argument?
gdoug
CC BY-SA 4.0
2022-10-05T19:36:54.347Z
"Randomized Algorithms" by Raghavan & Motwani. The entire book is worth reading, but you need only Section 5. Basically, you need to use that $\mathbb E[X] \le \max X$ for any random variable $X$.
Dmitry
CC BY-SA 4.0
2022-10-06T08:23:09.863Z
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.
Emil Jeřábek
<cc.complexity-theory><sat>
3SAT instances where no assignment fails to satisfy more than one clause: do they eixst, and what complexity class do they belong in?
gdoug
# 3SAT instances where no assignment fails to satisfy more than one clause: do they eixst, and what complexity class do they belong in?

(Asked by: username_0 on 2022-10-04)

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?

**Tags:** cc.complexity-theory, sat

> **Comments:**
> **username_1**: Can you describe the motivation? One trivial example is $(x \lor x \lor x) \land (\bar x \lor \bar x \lor \bar x)$.  
> **username_1**: By the probabilistic argument, you can show that each such instance has at most $8$ non-trivial (i.e. not always true) clauses.  
> **username_0**: 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.  
> **username_0**: @username_1 do you mind providing any resources on this probabilistic argument?  
> **username_1**: "Randomized Algorithms" by Raghavan & Motwani. The entire book is worth reading, but you need only Section 5. Basically, you need to use that $\mathbb E[X] \le \max X$ for any random variable $X$.  
> **username_2**: 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.  

---

## 0 answers

