<p>Given a 3SAT problem with the additional constraints that:</p>
<ol>
<li><p>No clause or set of clauses is the 3SAT instance is '<em>redundant</em>'. Thus, this 3SAT cannot eliminate any clauses.</p>
</li>
<li><p>For any/every clause, the triplet of 3 variables in it are guaranteed to occur in at least 1 other clause.</p>
</li>
</ol>
<p>What is the computational complexity of this 3SAT variant?</p>
<p><strong>Redundant Clause</strong> - A clause is redundant if its elimination from the problem does not change the set of valid solutions of the problem. For eg: <span class="math-container">$(a\vee b \vee c) \wedge (a\vee b) \wedge (a\vee c)$</span>. The first clause is redundant here as it does not affect the set of valid solutions of this problem.</p>

CC BY-SA 4.0
2021-10-29T18:38:37.067Z
Do you intend this to be a promise problem?  That is, an algorithm only needs to return the correct answer if the input meets the additional constraints, and otherwise the algorithm can return any answer?
Neal Young
CC BY-SA 4.0
2021-10-29T19:52:06.153Z
related: https://cstheory.stackexchange.com/questions/50452/3sat-to-1-in-3sat-reduction-with-additonal-constraints
Neal Young
CC BY-SA 4.0
2021-10-30T11:34:44.070Z
I think so. We are working under the assumption that both 1 and 2 are satisfied for any problem instance given to us.
J.Doe
CC BY-SA 4.0
2021-10-30T13:22:10.703Z
The Critical Satisfiability problem may be helpful here https://cstheory.stackexchange.com/questions/38715/variant-of-critical-sat?rq=1...
Neal Young
CC BY-SA 4.0
2021-10-30T13:48:07.023Z
Thank you. I just read it. The problem is similar but there are key differences: 1. Critical SAT is the problem that removal of any clause makes the problem satisfiable. Our problem states the set of valid solutions changes, we can't say the stronger statement that the problem becomes satisfiable like in critical SAT. 2. We have the second constraint too. Doesn't it make it different? –
J.Doe
CC BY-SA 4.0
2021-10-30T17:40:02.497Z
Yes, it's different.  But maybe some of the ideas used to show that Critical SAT is hard can be adapted to show your problem is hard too.
Neal Young
<cc.complexity-theory>
Computational Complexity of 3SAT variant with additional restrictions on variables/clauses
J.Doe
# Computational Complexity of 3SAT variant with additional restrictions on variables/clauses

(Asked by: username_0 on 2021-10-29)

Given a 3SAT problem with the additional constraints that:

1. No clause or set of clauses is the 3SAT instance is '*redundant*'. Thus, this 3SAT cannot eliminate any clauses.
2. For any/every clause, the triplet of 3 variables in it are guaranteed to occur in at least 1 other clause.

What is the computational complexity of this 3SAT variant?

**Redundant Clause** - A clause is redundant if its elimination from the problem does not change the set of valid solutions of the problem. For eg: $(a\vee b \vee c) \wedge (a\vee b) \wedge (a\vee c)$. The first clause is redundant here as it does not affect the set of valid solutions of this problem.

**Tags:** cc.complexity-theory
> **Comments:**
> **username_1**: Do you intend this to be a promise problem?  That is, an algorithm only needs to return the correct answer if the input meets the additional constraints, and otherwise the algorithm can return any answer?  
> **username_1**: related: https://cstheory.stackexchange.com/questions/50452/3sat-to-1-in-3sat-reduction-with-additonal-constraints  
> **username_0**: I think so. We are working under the assumption that both 1 and 2 are satisfied for any problem instance given to us.  
> **username_1**: The Critical Satisfiability problem may be helpful here https://cstheory.stackexchange.com/questions/38715/variant-of-critical-sat?rq=1...  
> **username_0**: Thank you. I just read it. The problem is similar but there are key differences: 1. Critical SAT is the problem that removal of any clause makes the problem satisfiable. Our problem states the set of valid solutions changes, we can't say the stronger statement that the problem becomes satisfiable like in critical SAT. 2. We have the second constraint too. Doesn't it make it different? –  
> **username_1**: Yes, it's different.  But maybe some of the ideas used to show that Critical SAT is hard can be adapted to show your problem is hard too.  

---

## 0 answers

