3
$\begingroup$

If I have $n$ variables and I want to write down all 3-SAT problems, the number of problems is $2^{8{n \choose 3}}$, since each clause has 3 variables and each variable can be negated or not.

But empirically with SAT solvers, the hardest SAT problems have far fewer terms than this (if you have too few or too many terms SAT is easy to solve).

I suspect there is a subclass of 3-SAT that grows like $2^{(c_0+c_1 n)}$ and is still NP-complete.

Does anyone know of such a class or have suggestions on how to construct it?

(update)

As pointed out, if we allow n clauses but each of the clauses can choose from whatever variable they want, we get $O(n^2)^n=2^{2 n log n+o(n log n)}$ possible problems.

It seems like we need some kind of windowed-3-SAT where there are $n*k$ clauses and clauses in the span $[k*i,k*(i+1)]$ can choose from variables $x_{i-w}$ to $x_{i+w}$. This gives us a finite number of choices for each clause and hence exponential growth in the number of problems (in n).

Is there some obvious reason this is/isn't NP-complete? (for W=0 it's obvious to me that it's not.And I could probably convince myself for w=1 it also isn't).

Trying out random problems with minisat, it looks like k=4..8 w=100+ is the regime where these problems are non-trivial. (-1 indicates a timeout of more than 1 second to solve). This is with n=100

enter image description here

Here are some solution times for random problems with k=4 w=100. For smaller w, the solution times look linear in n, but there's definitely something non-linear going on for w=100. I suspect that if there is true NP-hard behavior going on you can get it with a much smaller w but that for random problems the larger w makes it more likely that we find the hard problems.

enter image description here

Improve this question
$\endgroup$
9
  • 2
    $\begingroup$ Yes, but for boring padding reasons: it suffices to ignore all but $\sqrt{n}$ of the variables. But if you somehow rule out padding, my guess is that the new version would be open, as it feels close to an NP-complete average-case hard problem. $\endgroup$
    – Geoffrey Irving
    Commented Mar 17 at 19:54
  • $\begingroup$ You might want to have a look at Linear SAT: sciencedirect.com/science/article/pii/S0166218X18302695 — I think (though I have not done the math) that these constraints should lead to an exponential number of clauses. $\endgroup$
    – Steven Stadnicki
    Commented Mar 17 at 20:12
  • $\begingroup$ You say that the number of 3-SAT problems is $8({n\atop 3})$, but I would describe this as the number of 3-SAT clauses. A 3-SAT problem, after all (and which clearly you know), is a finite list of such clauses. $\endgroup$
    – Joel David Hamkins
    Commented Mar 17 at 21:36
  • 1
    $\begingroup$ I'm not convinced by your intuition — while each hard instance might only have $O(n)$ clauses, in total there are still $\binom{\binom{n}3}n = O(n^2)^n = 2^{2n\log n+o(n \log n)}$ problems, which is still quite a lot. It might be more reasonable to ask for that, though $\endgroup$
    – Daniel Weber
    Commented Mar 18 at 12:42
  • 1
    $\begingroup$ I haven't worked through the details, but I think that TSP on $n$ vertices can be reduced to 3SAT with $O(n^2)$ variables and $O(n^2)$ clauses. What I'm not sure is whether that addresses your question. Would "the set of problems produced by X reduction from a different NP-complete problem" be an acceptable answer in principle, if the details work out? $\endgroup$
    – Peter Taylor
    Commented Mar 18 at 20:18

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .