7
$\begingroup$

I've been looking for a reference for the above question.

As far as I know the answer is:

If we can make a solver that is efficient for all randomly generated instances, it should be efficient for any instance.

i.e. if we make a solver that doesnt rely on any inherent structure, it will always be efficient.

Is this correct? Either way, does anyone have a reference to a paper I can cite for the answer.

$\endgroup$
  • $\begingroup$ plz link to your thesis mentioned below if finished/ available online, or later if not done yet $\endgroup$ – vzn Jan 14 '15 at 17:57
  • $\begingroup$ @vzn, its not online yet, I'm hoping to have it finished by the end of the week. However, it wont be available online until after the SAT 2015 conference, as we are submitting some portions of the work there $\endgroup$ – Zack Newsham Jan 15 '15 at 7:42
9
$\begingroup$

If your solver is efficient for random 3-SAT, it by no means entails that it is efficient for an arbitrary 3-SAT instance. Randomly generated instances are very different from instances that arise in practice (meaning they are structured differently). For instance, you can read about the phase transition in random $k$-SAT: depending on the clause-to-variable ratio, an instance can be easy (not constrained enough, or too constrained) or hard (in some sense critically constrained). This phenomenon is rather fascinating in itself.

You can always argue that if you have a solver that does not exploit any structure of the input and is always rather magically efficient, much of the theory we have developed around SAT is useless. Unfortunately, many people have worked a lot on the problem, and we are still unable to give an efficient algorithm for e.g. SAT (not to mention an algorithm that would be efficient in practice as well!). So how do we cope with this? We look at e.g. structural aspects of the input: what can we leverage? How can we be fast at least sometimes? Because we can't solve a problem we care about, we look for other approaches and angles of attack.

I think the main reasons we have been interested in random $k$-SAT is that first, such instances are easy to generate to test our solvers. We have also learned that random instances are very different from instances that arise in practice (and of course those are the instances we often care about). This has increased our understanding of the nature of computation, heuristics, complexity, and ultimately made us able to build faster solvers as well.

$\endgroup$
  • $\begingroup$ I have done quite a bit of work in understanding SAT, and my thesis is based on community structure in SAT problems. My Co-supervisor (who is a systems prof, minimal SAT knowledge) asked the question "why do we care about the efficiency of solvers on random SAT problems" and it occurred to me I didn't know the answer. It seems that you are saying there is a non-direct link between efficient random solvers, and efficient industrial solvers, in that random solvers have provided insight into the complexity of the problem? $\endgroup$ – Zack Newsham Jan 13 '15 at 19:28
  • $\begingroup$ @ZackNewsham Not only that, but I think research on random SAT has been fruitful, for both theoretical computer scientists, physicists (phase transition, survey propagation), random graph theorists (rigorous mathematical results on SAT), ... So yes, definitely it has given us more insight into complexity and solving methods. $\endgroup$ – Juho Jan 13 '15 at 19:50
1
$\begingroup$

the other answer is good, here is a bit additional context & 2 papers as requested. the discovery of phase transitions in NP complete problems associated with random inputs was a striking scientific discovery at the time (mid 1990s), worthy of publication in a leading/ elite scientific journal, Science magazine, typically reserved for only very remarkable and cross-cutting discoveries by top scientists. phase transitions are normally seen/ studied mostly in physics and this discovery links theoretical physics areas such as thermodynamics theory with computer science theory, and is still being explored decades later, and there are now many dozens of papers on the subject. from Selmans own web site

another area where random inputs is now shown to play a significant role is in lower bounds proofs involving monotone circuits. Razborov won a TCS Nevanlinna prize for early work in this area now extended by Rossman.

another way to regard random inputs however is just more generally as one of the most basic input distributions that can be studied for statistical/ average case complexity, for any algorithm. for example with sorting algorithms and many others, an easy way to test them is with random inputs.

$\endgroup$
  • $\begingroup$ in short, a paradigm shift $\endgroup$ – vzn Jan 15 '15 at 5:41
  • $\begingroup$ Interesting stuff, but (without looking into too much detail at those papers) neither seems to address why we care about random - what does it matter if we can solve random instances quickly, if we can't solve (some) industrial ones at all? $\endgroup$ – Zack Newsham Jan 15 '15 at 7:43
  • $\begingroup$ oh. see the misconception. randomly generated instances are or are not (always) "quickly" solvable, depending on the "random" distribution. the transition point research explains why to some degree. the "real"/detailed answer must be close to a P=?NP proof. another concept that forgot to mention-- SAT solvers tend to take about the "same amount of time" on the same instances within constant factors. ie SAT solver time is somewhat highly correlated across solvers/ instances. ie apparently theres an instance "hardness" independent of solvers. $\endgroup$ – vzn Jan 15 '15 at 16:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.