Ranking the Difficulty of NP Hard Problems in Practice

Question

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!

Answer 1

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.