# Computational Complexity of 3SAT variant with additional restrictions on variables/clauses

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.

• 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? Oct 29, 2021 at 18:38
• Oct 29, 2021 at 19:52
• I think so. We are working under the assumption that both 1 and 2 are satisfied for any problem instance given to us. Oct 30, 2021 at 11:34
• The Critical Satisfiability problem may be helpful here cstheory.stackexchange.com/questions/38715/…... Oct 30, 2021 at 13:22
• 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. Oct 30, 2021 at 17:40