5
$\begingroup$

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.

Improve this question
$\endgroup$
6
  • 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
    Commented Oct 29, 2021 at 18:38
  • $\begingroup$ related: cstheory.stackexchange.com/questions/50452/… $\endgroup$
    – Neal Young
    Commented 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
    Commented Oct 30, 2021 at 11:34
  • 1
    $\begingroup$ The Critical Satisfiability problem may be helpful here cstheory.stackexchange.com/questions/38715/…... $\endgroup$
    – Neal Young
    Commented 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
    Commented Oct 30, 2021 at 17:40

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.