Return to Question

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

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 here. 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.

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

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.

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

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

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 here. 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.

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).

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