This question is tightly related to another post: Phase Transitions in NP Hard Problems but it is somewhat different. While that question is about the hardness of particular instances of NP hard problems, this is about ranking the difficulty of the same instances.

There is a lot of bibliography on the effect known as Phase Transition. In particular for the case of random 3-SAT formulae in Conjunctive Normal Form (CNF), it is known that there is a value R of the ratio of clauses to variables such that for all r < R the formula can be satisfied with high probability and for r > R the formula is unsatisfiable with high probability. The Phase Transition effect happens near R and it has the remarkable effect that solving the satisfiability problem for those formulas is extremely hard in practice.

Since for proving NP hardness of a given problem it is needed to show that there is a polynomial time Turing-reduction to it of an NP-complete problem and that problems that are NP-complete can be transformed in polynomial time among them, then the following question naturally arises:

Is it possible to rank the difficulty of NP hard problems in practice using the Phase Transition of 3-SAT CNF as an indicator? The intuition is that one problem P1 can be expected to be harder than P2 if its 3-SAT encoding is nearer R (which is known to be near 4.2). Note that this idea does not necessarily bound each particular instance to a particular difficulty, it just ranks them.

There are a number of counter arguments, among them:

  1. The Phase Transition of 3-SAT CNF formula applies to random formulae. However, a particular instance in a different problem has some structure that might be exploited by solvers for that problem ---this was already pointed out by Peter Shor in the aforementioned question.
  2. It might be the case that the particular encoding used for transforming the particular instances in our problem to 3-SAT plays a crucial role in the ratio of clauses to variables leading to misleading values, hence misclassifications ---this concern is raised by Kaveh in the comments to this question.
  3. Serge (according to my understanding from his comment to this question) raises the issue that one might artificially complicate the original NP hard problem so that it results in a 3CNF formula that alters the ratio of clauses to variables while preserving the satisfiability.

As for 1, all problems might share the same class of regularity so that ranking problems (instead of characterizing the difficulty) might apply; as for 2, there are encodings in particular problems which are known to be non-redundant w.r.t the Unit Propagation rule so that those should be preferred and maybe they avoid those misclassifications. An example is Sideris et al., 2010 for the case of Propositional Planning. As for 3, Cheeseman et al., 1991 already considered the issue of whether mappings between problems preserve or not the phase transition effect and their preliminary experiments seem to support their conjecture, provided that one reduces the original NP problem and even that "can be further reduced by applying resolution to the clauses".

Do this all make sense to you? are you aware of any bibliographical references about this? Any guidance would be largely acknowledged!

  • $\begingroup$ I would guess the answer would depend on the particular reduction to SAT that one uses though there might be a way to get around that. $\endgroup$ – Kaveh Nov 27 '11 at 13:37
  • 5
    $\begingroup$ One more counter argument is that one can always add a very sparse or a very dense satisfiable disjoint component to a 3CNF formula, altering the ratio of clauses to variables and preserving its satisfiability. $\endgroup$ – Serge Gaspers Nov 27 '11 at 14:09
  • $\begingroup$ @Kaveh: thanks a lot for your comments! The idea would be using non-redundant encodings to 3-SAT as in [Sideris et al. 2010]. I am not claiming that this will work, but it seems to be the right thing to do. I have edited the question with your comment. Thanks again! $\endgroup$ – Carlos Linares López Nov 28 '11 at 20:57
  • 1
    $\begingroup$ @Serge: good point Serge! [Cheesemann et al., 1991] already examined the question of whether mappings between problems preserve the phase transition effect both for NP problems and problems in P (to prove that they do not become NP when been artificially extended to 3-SAT, for example) and their results support those claims provided that they start with some preliminary reductions, maybe applying the Unit Propagation rule. I have edited my question with your comments. Thanks a lot! $\endgroup$ – Carlos Linares López Nov 28 '11 at 20:59
  • $\begingroup$ @all: thank you very much for the attention given to my question! It is my first question here (and I will surely post others in the future). I found it impressive that in less than 24 hours it received 125 visits, 7 votes and one person marked it as fav. Thanks to you all! $\endgroup$ – Carlos Linares López Nov 28 '11 at 21:15

While it's not inconceivable that the technical obstacles you mention could be overcome somehow, I think that there is very little motivation at present to do so, for the simple reason that (at least as far as I am aware) the difficulty of NP-hard problems in practice seems, empirically, to have little to do with their closeness to the 3-SAT phase transition.

Contrast this with some other ways to rank NP-hard problems in terms of difficulty: There is some empirical correlation between NP-hard problems that are easy in practice and NP-hard problems that are easy to approximate, or that are fixed-parameter tractable (in the sense of parameterized complexity). Appropriate notions of reduction have been developed in these cases that partially explain the empirical observations. However, there currently seems to be no empirical indication that most NP-hard problems that are difficult in practice are difficult because of their close relationship to 3-SAT instances near the phase transition. So it does not make too much sense to develop a theory to "explain" something that does not appear to be true in practice.

  • 2
    $\begingroup$ Upvoted. I would be interested in a reference to empirical ranking of NP-hard problems. $\endgroup$ – Aaron Sterling Nov 29 '11 at 19:34
  • $\begingroup$ Upvoted as well! But as Aaron, I would be very interested also in some reference bibs about ranking of NP-hard problems. Give me a couple and I will happily mark this question as being answered! (sincerely speaking I will surely do in a couple of days even if you do not provide any bib references) Thanks again Timothy! $\endgroup$ – Carlos Linares López Nov 29 '11 at 21:00
  • 1
    $\begingroup$ @CarlosLinaresLópez : Fundamentals of Parameterized Complexity by Downey and Fellows (Springer, 2013) gives some information about the $W$-hierarchy of parameterized complexity. Approximation Algorithms for NP-Hard Problems by Dorit Hochbaum (ed.) ranks some NP-hard problems by difficulty of approximation. Hochbaum's book is a bit old so you may also want to look at more recent books on approximation algorithms. $\endgroup$ – Timothy Chow Jan 24 at 16:49
  • $\begingroup$ Timothy!! Thanks a lot really!!! It is very kind of you providing that bib reference!! Thank you so much!! $\endgroup$ – Carlos Linares López Jan 24 at 19:23

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.