2
$\begingroup$

Consider a restriction on 3-SAT in which no literal occurs in more than two clauses. How do we show that this is NP complete ?

(edit - I was getting confused over the definition on the 3-SAT,here by 3-SAT it implies that a clause can have at most 3 literals.)

Improve this question
$\endgroup$
7
  • $\begingroup$ By giving a suitable polynomial-time reduction. Or did you try that already and got stuck somewhere? $\endgroup$
    – Juho
    Commented Apr 16, 2018 at 17:11
  • $\begingroup$ I try to do the method in which we prove the NP completeness of 3-SAT but stuck in this one $\endgroup$
    – RajieRoo
    Commented Apr 16, 2018 at 17:11
  • 1
    $\begingroup$ Well if you provide a way to rewrite 3SAT in polynomial time to this restricted 3SAT, then you are done. So you need to design such rewrite algorithm. You can for instance introduce new SAT variables (as long as the number of such variables scales polynomial with the input, then there is no problem). $\endgroup$
    – willeM_ Van Onsem
    Commented Apr 16, 2018 at 17:15
  • 3
    $\begingroup$ We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. You might find this page helpful in improving your question. I suggest you also spend some time trying to find a polynomial-time algorithm; don't just limit yourself to proving it NP-complete. Finally, what's the context where you encountered this problem? Please credit the source of the exercise or where you ran into it, in the question. $\endgroup$
    – D.W. ♦
    Commented Apr 16, 2018 at 17:45
  • 1
    $\begingroup$ Do you mean no variable appears twice or no literal appears twice? That is, can it be that $x_i$ appears twice and $\bar{x}_i$ also appears twice? $\endgroup$
    – Yuval Filmus
    Commented Apr 16, 2018 at 18:02

1 Answer 1

Reset to default
2
$\begingroup$

I have found a reduction from 3-SAT.

For every instance of variable $y$, I will put a new variable $y_i$ in its place. Suppose there were $K$ such instances then after replacing each instance of $y$, I will add clauses $\bar y_1 \vee y_2, \bar y_2 \vee y_3, \ldots, \bar y_K \vee y_1$. This ensures that $y_1,\ldots,y_K$ will be assigned the same value.

Improve this answer
$\endgroup$
0

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.