Where the Really Hard Problems Went

Many if not all NP problems show a solvability phase transition along a secondary parameter for any fixed input size. These secondary parameters and associated solvability phase transitions have been identified and in many cases, the solving algorithms used for these problems require significantly more time for instances close to this phase transition.

This hardness-near-the-phase-transition-phenomenon has profound implications for the NP-completeness of the problems themselves. Being a member of the class \emph{NP} implies that a problem has no exact algorithm of subexponential runtime for the worst case instances for increasing input size. But these worst case instances are rather scarce, and appear to reside around the solvability phase transition. For this reason, further study of this phenomenon is warranted. In this dissertation, we will four different problems in NP: the Hamiltonian cycle problem, the asymmetric traveling salesman problem, the partition problem and the perfect rectangle problem.

For the Hamiltonian cycle problem, we show that very rare but super hard instances exist very far from the solvability phase transition. These instances display a degree of universal hardness, requiring vast amounts of runtime for all major published exact backtracking algorithms. But we also replicate earlier results for this problem, showing that in randomly generated ensembles, the hardest instances are all located near the solvability phase transition. We conjecture, by an argument from Kolmogorov complexity, that these super hard instances, which are highly structured, are very unlikely to show up in randomized ensembles, solving the paradox. These results could encourage the community to explore the influence of an instance structure on hardness.

For the asymmetric traveling salesman problem, we also replicated earlier results, claiming the standard deviation of the random instance generation function for the values in the cost matrix could be used as a secondary parameter for the problem's instance hardness. These results however, turned out to be flawed. The culprit is an interplay between the lognormal generation function and an ensuing integer roundoff for the matrix values. We show that the hardness difference for the instances almost completely disappears when the roundoff is omitted, but we also show that when the roundoff is preserved, the resulting number of zeroes in the matrix is directly related to the aforementioned standard deviation.

For the partition problem, a secondary parameter can be found in the number of bits per integer in the set. If this ratio is low, the instance typically has many perfect solutions, and one is easily found. If this ratio is high, the entire search tree must be traversed to find the optimal split. In our contribution, we show that the problem's algorithmic hardness does not only depend on the absolute magnitude of bits per integer, but also on their actual distribution. The results however do invoke other questions on the hardness of this problem in NP, namely whether a deliberate search for distributions instead of instances can identify hard regions, but also whether easy and hard instances can be separated, as the solution distribution in the instance space might be fractally structured.

For the perfect rectangle packing problem, we identified a secondary parameter in the parameter `randMax', which determines the maximum side length of the rectangles in an instance. The midpoint of this phase transition lies very close to O(n sqrt(n)), which is very different from other phase transition midpoints. It begs further investigation, but the problem is much harder than the other NP-complete problems in this thesis, and demands significantly more time and space.