A Caltech Library Service

Characterizing NP and Measuring Instance Complexity

Judd, Stephen (1990) Characterizing NP and Measuring Instance Complexity. California Institute of Technology . (Unpublished)

See Usage Policy.

Other (Adobe PDF (571KB))
See Usage Policy.


Use this Persistent URL to link to this item:


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.

Item Type:Report or Paper (Technical Report)
Group:Computer Science Technical Reports
Record Number:CaltechCSTR:1990.cs-tr-90-11
Persistent URL:
Usage Policy:You are granted permission for individual, educational, research and non-commercial reproduction, distribution, display and performance of this work in any format.
ID Code:26727
Deposited By: Imported from CaltechCSTR
Deposited On:25 Apr 2001
Last Modified:03 Oct 2019 03:17

Repository Staff Only: item control page