I've tried to prove it for several days but I can't make sure if it is equivalent to max-3-SAT problem? This problem seems similar to the proof of SAT ∝ 3-SAT except the case where there are more than 3 literals in each clause. so, we could prove that a clause with more than 3 literals could be broken into several 3-SAT.

for example

& x2 ∨ x3
& x4 ∨ x5 ∨ x6
& x7 ∨ x8 ∨ x9 ∨ x10 ∨ x11

This is a typical SAT problem. If we could break the last clause into several clauses and prove they are equal to the original, then we prove SAT ∝ ≤3SAT.

Fortunately, the way to break last clause into 3-SAT is exactly the same with how it is done in SAT ∝ 3SAT.

That is, we add y1 and y2 and make the last clause become

x7  ∨  x8  ∨  y1
x9  ∨ -y1  ∨  y2 
x10 ∨  x11 ∨ -y2

suppose they are denoted S' and the original clause is S. and, if S is satisfiable, then S' is satisfiable and if S' is satisfiable, then S is satisfiable

Since SAT, which is NP-complete, is polynomially reduced to ≤3SAT, ≤3SAT is also NP-complete.

However, The above proof is quite trivial if we already understand the proof of SAT ∝ 3-SAT.

is there any general proof that could solve 3-SAT, ≤3SAT, n-SAT, ≤nSAT simultaneously?


  • $\begingroup$ We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. $\endgroup$ – D.W. Jun 12 '16 at 7:46
  • $\begingroup$ Our reference question is likely to be helpful. $\endgroup$ – Juho Jun 12 '16 at 8: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.