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.

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


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.