0
$\begingroup$

I have a question. SAT in which all the clauses have three variables (3-SAT) is more difficult than a traditional SAT which may also include clauses one and two variables? (Of course there are also clauses of the three variables but not all have three variables. More than 3 variables in clauses not exist.)

After my converted a traditional SAT to 3-SAT, analysis of the problem 3-SAT is more difficult for SAT solvers? Meybe it not change anything?

It may seem strange but I want to get after the conversion specified function was difficult as possible.

$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

In general we are talking about worst-case complexity for a problem. Every instance of 3-SAT is an instance of SAT, which means that an algorithm to solve SAT must solve 3-SAT. In this sense, SAT is at least as hard as 3-SAT. On the other hand, the fact that there is a polynomial-time reduction from SAT to 3-SAT means that 3-SAT is at least as hard as SAT.

A particular algorithm for SAT might perform better or worse on an instance of SAT than on the reduction of that instance to 3-SAT. My guess is that usually a good SAT solver would be worse on the reduction to 3-SAT. This may be of some practical interest, but it has no bearing on the theoretical aspects of complexity theory.

$\endgroup$
3
  • $\begingroup$ we usually reduce specific problem to generic problem (like Turing Machine accepts specific string to Turing Machine halting problem). As per this logic, we should be able to reduce 3SAT to SAT, not other way around. But does the fact that reductions in both directions exist (they do, right?) means both are of equal hardness or at least their hardness does not differ vastly? $\endgroup$
    – RajS
    Dec 9, 2019 at 5:03
  • $\begingroup$ If there was a polynomial-time algorithm for 3SAT we could use the reduction to get a polynomial-time algorithm for SAT. They're not really "of equal hardness" though: the degree of the polynomial would almost certainly be different. But since we don't have a polynomial-time algorithm for 3SAT, things are even worse: an exponential-time algorithm for 3SAT might take vastly more time (say $2^{n^2}$ as opposed to $2^n$) on the reduction of a size-$n$ SAT problem than it would on a size-$n$ 3SAT problem. $\endgroup$
    – Robert Israel
    Dec 9, 2019 at 17:00
  • $\begingroup$ yes thats fine. My point was I was unaware of the fact that generic problems are / can be also reduced to specific problem. Till now I was of opinion that only specific (comparatively easier) problems are reduced to generic (comparatively harder) problems. It seems that I was incorrectly interpreting reduction symbol as $<$ and thinking that problem on left hand side of $<$ must be easier than the one on right hand side. But the reduction symbol is $\leq$, So, I guess in $SAT \leq 3SAT$, that $=$ in $\leq$ is getting into play. $\endgroup$
    – RajS
    Dec 9, 2019 at 18:17

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .