Characterizing NP and Measuring Instance Complexity

Judd, Stephen (1990) Characterizing NP and Measuring Instance Complexity. Technical Report. California Institute of Technology. [CaltechCSTR:1990.cs-tr-90-11]

Full text available as:

	Postscript - Requires a viewer, such as GhostView
	Other (Adobe PDF (571KB))

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.

EPrint Type:	Monograph (Technical Report)
Subjects:	All Records
ID Code:	72
Deposited By:	Caltech Library System
Deposited On:	25 April 2001
Record Number:	CaltechCSTR:1990.cs-tr-90-11
Official Persistent URL:	http://resolver.caltech.edu/CaltechCSTR:1990.cs-tr-90-11
Usage Policy:	You are granted permission for individual, educational, research and non-commercial reproduction, distribution, display and performance of this work in any format.

Archive Staff Only: edit this record