2
$\begingroup$

This post introduces a new variant of 3-SAT called EQUAL-3-SAT where the number of clause is same as number of variables, and it is shown to be NP-complete.

I want to ask if the monotone version of this EQUAL-3-SAT is also NP-complete ,by monotone ,I mean where each clause can either contain all positive or all negative literals.

We can reduce 3-SAT instance to monotone-3-SAT but I don't understand how to maintain the "clause is equal to number of variables" property when converting 3-SAT into monotone-3-SAT

Motivation : The EQUAL-3-SAT is one of the most restrictive variant of 3-SAT I've seen yet ,with respect to the number of clauses it needs as an input ,thus I was wondering if this kind of restriction maintains its compleixty status when we try to make the variable overlappings between clauses less complex ,by adding the monotone condition ,we can make the overlappings less complex as every clauses is either all true or all false .

Does there exist a reduction from EQUAL-3-SAT to monotone-EQUAL-3-SAT ?

Improve this question
$\endgroup$
13
  • $\begingroup$ I noticed you've asked a fair number of questions of the form "is this variant of SAT NP-complete/#P-hard/...?" It's possible you might be more likely to get answers if you provide some motivation in each post about why each particular variant is important and motivate its relevance. Anyone can come up with a lot of variants, but I'm not sure whether it will be useful to others in the future to have a long list of questions asking about each possible variant one could imagine. $\endgroup$
    – D.W. ♦
    Commented Jun 15, 2023 at 16:54
  • $\begingroup$ Sure. I will add my motivation behind my question from now on. $\endgroup$
    – Anuj
    Commented Jun 15, 2023 at 16:56
  • 1
    $\begingroup$ Try reducing monotone-3-SAT to monotone-EQUAL-3-SAT using the ideas given here. It is easy. $\endgroup$
    – Inuyasha Yagami
    Commented Jun 15, 2023 at 20:33
  • $\begingroup$ @InuyashaYagami yeah ,we can reduce monotone-3-SAT to monotone-EQUAL-3-SAT using those methods ,Thanks for the advice. $\endgroup$
    – Anuj
    Commented Jun 16, 2023 at 16:05
  • 1
    $\begingroup$ Yes, there will be duplicates. If you want to avoid that you can add a new clause $(x \lor y )$ where $x$ is the new variable and $y$ is an existing variable. Since $n > m$, there exists sufficient number of such $y$'s. $\endgroup$
    – Inuyasha Yagami
    Commented Jun 16, 2023 at 18:26

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.