My understanding is that if we have a totally random k-SAT formula, for a ratio $m < \alpha n$ far enough below the satisfiability threshold, we can solve for satisfiability in polynomial time (with a high probability of success as $n$ tends to infinity).

What I'm curious about, and which I guess is the beginner's question, is what happens if we increase $k$, $m$, and $n$. To elaborate, we can suppose that the original formula is significantly above the threshold, and therefor no polynomial method is guaranteed. However, the new increase in $k$ puts the formula significantly below the threshold, and so if the new formula was random, it could be solved in time polynomial in the new $n$.

However, the new formula is not random. It's based on the old one. So it seems that the polynomial methods don't apply. My curiosity is, if we could generate several formulas with increased $k$, $m$, and $n$, below the threshold, they may in some way be considered random. So perhaps the randomness criterion can be satisfied. I'm wondering if there is any way to prove this...


Perhaps what I'm really after is finding out what constitutes randomness in satisfiability instances. Of course it's a random formula with the proper parameters, but doesn't this mean that if we can repeatedly generate formulas with the same parameters, they can be considered random?

I'm really hoping that someone can give me a better perspective on things. I keep wondering if there's some way to modify SAT formulas to take advantage of polynomial methods.

  • 1
    $\begingroup$ Random k-SAT is usually with respect to a uniform distribution over all possible inputs. If you are generating instances randomly from one regime, but then reducing these to instances satisfying a different relationship between the parameters, then those are no longer uniformly distributed in the class defined by the new parameters. $\endgroup$ Apr 10, 2015 at 12:18
  • $\begingroup$ @AndrásSalamon: My concern is that in the '08 Handbook of Satisfiability, page 247, there is a lower bound for which "a polynomial-time algorithm has been proven to find satisfying assignments". I was wondering if this means that any CNF k-SAT formula below this threshold can be solved in polynomial time (at least with high probability). Here's a link: users.soe.ucsc.edu/~optas/papers/handbook.pdf $\endgroup$
    – Matt Groff
    Apr 10, 2015 at 16:04
  • $\begingroup$ there are prob many different ways to answer this question. one misconception is mixing up statistics samples associated with transition point behavior with a single instance. a single instance cannot be said to have any statistical property, only that it is from a sample with some aggregate property. another pov, hard & easy instances are actually mixed in a fractal-like pattern for all non-narrow choices of parameters. another idea is that indeed there are transformations between instances in different "sizes" but this can only lead to an efficient algorithm if P=NP. etc $\endgroup$
    – vzn
    Apr 11, 2015 at 0:44


Your Answer

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

Browse other questions tagged or ask your own question.