# Did “Where the really hard problems are” hold up? What are current ideas on the subject?

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?

• Random instances of CSP, k-sat, k-coloring have been extensively studied by the TCS community. For example, the fact that the density/'constrainedness' at which we can efficiently solve a particular problem is often lower than the threshold at which the probability of a solution existing goes from 1 to 0 w.h.p. has attracted a lot of attention. – JWM Jan 23 '17 at 10:35
• At what probability does the threshold of 'easy solvability' lie (roughly speaking)? Is it more like 0.2 or more like 0.001? – dimpol Jan 23 '17 at 12:20
• @dimpol usually no such precise threshold is defined. The point is at what "constrainedness" does the probability go to 0 or 1 with the input size. A typical statement would be, "Algorithm A solves a random 3-SAT instance with $n$ variables and $\Delta n$ clauses with probability at least $p_n$, where $p_n$ goes to 1 with $n$." The threshold is the value of $\Delta$ for which the probability goes from tending to 0 to tending to 1. – Sasho Nikolov Jan 23 '17 at 17:26
• think the ideas have been very influential in general and there is a very large set of papers related to this topic and research continues. however, its a crosscutting concept because phase transitions come more from physics and (re MATs answer below) maybe computer scientists are a little more skeptical about their significance, and also it seems possibly more an empirical/ experimental concept. might try to work up an answer at some pt if others agree with this comment, but for now invite/ would defn highly encourage further discussion/ analysis in Theoretical Computer Science Chat – vzn Jan 25 '17 at 16:35
• see also how common is phase transition in NP complete problems. also think Walsh 1998 the constrainedness knife edge is significant & hasnt been followed up on much, its interrelated to the transition point but maybe not exactly the same concept... the paper does not mention fractals directly but think its highly suggestive in its ref to self-similarity, scale invariance etc. – vzn Jan 26 '17 at 3:55

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.

• Thanks for the overview, a pity that this didn't lead to any real breakthroughs. – dimpol Jan 23 '17 at 14:58
• I think shattering phenomenons can be considered to rule out a class of local search based algorithms that are the base of many heuristic algorithms for NP-hard problems. – Kaveh Jan 23 '17 at 20:48
• similar/ somewhat revised talk/ video by Vardi, 2014, phase transitions & computational complexity, Banff international research station – vzn Jan 26 '17 at 3:46
• @vzn Nice, must watch video by Vardi. – Mohammad Al-Turkistany Jan 26 '17 at 3:50

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.

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

• This is not the right place to present unpublished research. Write a paper explaining everything in detail, put it on arxiv or somewhere else, and post a link here with a summary. – Sasho Nikolov Feb 11 '17 at 8:08
• The C4D9 regular graph coloring point is an extreme hard spot, as per the title in the question. It needed a little context, thus the rest of the table. – daniel pehoushek Feb 11 '17 at 19:37