Did "Where the really hard problems are" hold up? What are current ideas on the subject?

Question

I found this paper to be very interesting. To summarize: it discusses why in practice you rarely find a worst-case instance of a NP-complete problem. The idea in the article is that instances usually are either very under- or very overconstrained, both of which are relatively easy to solve. It then proposes for a few problems a measure of 'constrainedness'. Those problems appear to have a 'phase transition' from 0 likelihood of a solution to 100% likelihood. It then hypothesizes:

1. That all NP-complete (or even all NP-problems) problems have a measure of 'constrainedness'.
2. That for each NP-complete problem, you can create a graph of the probability of a solution existing as a function of the 'constrainedness'. Moreover, that graph will contain a phase-transition where that probability quickly and dramatically increases.
3. The worst case examples of the NP-complete problems lie in that phase-transition.
4. The fact whether a problem lies on that phase-transition remains invariant under transformation of one NP-complete problem to another.

This paper was published in 1991. My question is was there any follow-up research on these ideas the last 25 years? And if so, what is the current mainstream thinking on them? Were they found correct, incorrect, irrelevant?

Answer 1

Here is a rough summary of the status based on a presentation given by Vardi at a Workshop on Finite and Algorithmic Model Theory (2012):

It was observed that hard instances lie at the phase transition from under- to over-constrained region. The fundamental conjecture is that there is strong connection between phase-transitions and computational complexity of NP problems.

Achlioptas–Coja-Oghlan, found that there is a density in the satisfiabe region where the solution space shatters into exponentially many small clusters. Vinay Deolalikar based his famous attempt to proof $P \ne NP$ on the assumption that shattering implies computational hardness. Deolalikar’s Proof was refuted by the fact that XOR-SAT is in $P$ and it shatters. Therefore, shattering can not be used to prove computational hardness.

The current mainstream thinking seems to be (as stated by Vardi) that phase-transitions are not intrinsically connected to computational complexity.

Finally, Here is an article published in Nature which investigates the connection between phase-transitions and computational hardness of K-SAT.

Answer 2

Yes, there has been a lot of work since Cheeseman, Kanefsky and Taylor's 1991 paper.

Doing a search for reviews of phase transitions of NP-Complete problems will give you plenty of results. One such review is Hartmann and Weigt [1]. For a higher level introduciton, see Brian Hayes American Scientist articles [2] [3].

Cheesemen, Kanefsky and Taylor's 1991 paper is an unfortunate case of computer scientists not paying attention to the mathematics literature. In Cheeseman, Kanefsky and Taylor's paper, they identified the Hamiltonian Cycle as having a phase transition with a pickup in search cost near the critical threshold. The random graph model they used was Erdos-Renyi random graph (fixed edge probability or equivalently Gaussian degree distribution). This case was well studied before Cheeseman et all's 1991 paper with known almost sure polynomial time algorithms for this class of graph, even at or near the critical threshold. Bollobas's "Random Graphs" [4] is a good reference. The original proof I believe was presented by Angliun and Valiant [5] with further improvements by Bollobas, Fenner and Frieze [6]. After Cheeseman, Kanefsky and Taylor, Culberson and Vandegriend [7] published a paper giving an algorithm that in practice performed extremely well for all Erdos-Renyi random graphs, even near the critical threshold.

The phase transition for Hamiltonian Cycles in random Erdos-Renyi random graphs exists in the sense that there is a rapid transition of the probability of finding a solution but this does not translate to an increase in "intrinsic" complexity of finding Hamiltonian Cycles. There are almost sure polynomial time algorithms for finding Hamiltonian Cycles in Erdos-Renyi random graphs, even at the critical transition, both in theory and in practice.

Survey propagation [8] has had good success in finding satisfiable instances for random 3-SAT very near the critical threshold. My current knowledge is a little rusty so I'm not sure if there's been any large progress of finding "efficient" algorithms for unsatisfiable cases near the critical threshold. 3-SAT, as far as I know, is one of the cases where it's "easy" to solve if it's satisfiable and near the critical threshold but unknown (or hard?) in the unsatisfiable case near the critical threshold.

My knowledge is a bit dated now but the last time I looked at this subject in depth, there were a few things that stood out to me:

• Hamiltonian Cycle is "easy" for Erdos-Renyi random graphs. Where are the hard problems for it?
• Number Partition should be solvable when very far in the almost sure probability 0 or 1 region but no efficient algorithms (to my knowledge) exist for even moderate instance sizes (1000 numbers of 500 bits each is, as far as I know, completely intractable with state of the art algorithms). [9] [10]
• 3-SAT is "easy" for satisfiable instances near the critical threshold, even for huge instance sizes (millions of variables) but hard for unsatisfiable instances near the critical threshold.

I hesitate to include it here as I have not published any peer reviewed papers from it but I did write my thesis on the subject. The main idea is that a possible class of random ensembles (Hamiltonian Cycles, Number Partition Problem, etc.) that are "intrinsically hard" are ones that have a "scale invariance" property. Levy-stable distributions are one of the more natural distributions with this quality, having power law tails, and one can choose random instances from NP-Complete ensembles that somehow incorporate the Levy-stable distribution. I gave some weak evidence that intrinsically difficult Hamiltonian Cycle instances can be found if random graphs are chosen with a Levy-stable degree distribution instead of a Normal distribution (i.e. Erdos-Renyi). If nothing else it will at least give you a starting point for some literature review.

[1] A. K. Hartmann and M. Weigt. Phase Transitions in Combinatorial Optimization Problems: Basics, Algorithms and Statistical Mechanics. Wiley-VCH, 2005.

[2] B. Hayes. The easiest hard problem. American Scientist, 90(2), 2002.

[3] B. Hayes. On the threshold. American Scientist, 91(1), 2003.

[4] B. Bollobás. Random Graphs, Second Edition. Cambridge University Press, New York, 2001.

[5] D. Angluin and L. G. Valiant. Fast probabilistic algorithms for Hamilton circuits and matchings. J. Computer, Syst. Sci., 18:155–193, 1979.

[6] B. Bollobás, T. I. Fenner, and A. M. Frieze. An algorithm for finding Hamilton paths and cycles in random graphs. Combinatorica, 7:327–341, 1987.

[7] B. Vandegriend and J. Culberson. The G n,m phase transition is not hard for the Hamiltonian cycle problem. J. of AI Research, 9:219–245, 1998.

[8] A. Braunstein, M. Mézard, and R. Zecchina. Survey propagation: an algorithm for satisfiability. Random Structures and Algorithms, 27:201–226, 2005.

[9] I. Gent and T. Walsh. Analysis of heuristics for number partitioning. Computational Intelligence, 14:430–451, 1998.

[10] C. P. Schnorr and M. Euchner. Lattice basis reduction: Improved practical algorithms and solving subset sum problems. In Proceedings of Fundamentals of Computation Theory ’91, L. Budach, ed., Lecture Notes in Computer Science, volume 529, pages 68–85, 1991.

Answer 3

25 years of study, and where are the current ideas:

+++ idea 1:

In my experience at satisfiability solving, I have found in practice that adding a valid k-clause to a formula that we are trying to solve is similar to deciding an (n-k) variable qbf.

That would seem to be an approach to showing current sat solving methods for NP are pspace-hard!

+++ idea 2:

Another idea is that the AllQBFs problem is a real problem in the boolean hierarchy. The AllQBFs problem is: Produce a boolean expression Q that decides all 2^n qbfs of a formula R. AllQBFs is easy when the original formula R is monotone or 2-cnf.

AllQBFs seems like a plausible road to showing QBF is Exp, because Q is often exponential, so evaluating an assignment of Q (a quantification of the original formula R) is exponential. So the road to proving NP is Exp at least has a couple bricks in it.

+++ idea 3: Regular k-cnfs

Btw, all the phase transition studies have missed Regular k-cnfs, where the number of occurrences of a variable (in either direction) is fixed, similar to degree regular graphs... Regular k-cnfs get much harder than the standard model, because all variables look identical in terms of constraints on them.

Twenty five years ago, just after reading cheeseman, I focussed on degree regular graph coloring, because all the variables look the same. So I will abuse my answer privilege here, and present twentyfive years of results on regular graphs!

+++ idea 4: Golden Points for satisfiability benchmark studies

I have studied C coloring of D regular N vertex graphs quite extensively. The following table summarizes the Golden Point results for regular graph coloring.

For High Probability, N random instances were satisfiable. For Very High, N^2 were satisfiable. For Super High, N^3 random instances were satisfiable.

The High Probability (1 - 1/N) golden coloring points are:

C3D5N180 C4D6N18 C4D7N35 C4D8N60 C4D9N180? C5D10N25 C5D11N42 C5D12N72

The Very High Probability (1 - 1/(N^2)) golden coloring points are:

C3D5N230? C4D6N18 C4D7N36 C4D8N68 C4D9N??? C5D10N32 C5D11N50 C5D12N78

The Super High Probability (1 - 1/(N^3)) golden coloring points are:

C3D5N??? C4D6N22 C4D7N58 C4D8N72? C4D9N??? C5D10N38 C5D11N58 C5D12N??

The C4D9 entry denotes four coloring of ninth degree graphs. These are the hardest random 4cnfs I have encountered in 25 years of sat solving. I recently colored a 172 vertex ninth degree graph after ten days of cpu time.

+++ Idea 5: The C5D16N???? Golden Point is mildly conjectured to exist.

Thanks, Daniel Pehoushek