Characterizing NP and Measuring Instance Complexity

Abstract

A generic NP-complete graph problem is described. The calculation of certain predicate on the graph is shown to be both necessary and sufficient to solve the problem and hence the calculation must be embedded in every algorithm solving NP problems. This observation gives rise to a metric on the difficulty of solving an instance of the problem. There appears to be an interesting phase transition in this metric when the graphs are generated at random in a "2-dimensional" extension. The metric is sensitive to 2 parameters governing the way graphs are generated: p, the density of edges in the graph, and K, related to the number of points in the graph. The metric seems to be finite in part of the (p,K)-space and infinite in the rest. If true, this phenomenon would demonstrate that NP-complete problems are truly monolithic and can easily exhibit strong intrinsic coupling of their variables throughout the entire instance.