Judd, Stephen (1990) Characterizing NP and Measuring Instance Complexity. California Institute of Technology . (Unpublished) http://resolver.caltech.edu/CaltechCSTR:1990.cstr9011

Postscript
See Usage Policy. 675Kb  

Other (Adobe PDF (571KB))
See Usage Policy. 557Kb 
Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechCSTR:1990.cstr9011
Abstract
A generic NPcomplete 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 "2dimensional" 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 NPcomplete 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.cstr9011 
Persistent URL:  http://resolver.caltech.edu/CaltechCSTR:1990.cstr9011 
Usage Policy:  You are granted permission for individual, educational, research and noncommercial reproduction, distribution, display and performance of this work in any format. 
ID Code:  26727 
Collection:  CaltechCSTR 
Deposited By:  Imported from CaltechCSTR 
Deposited On:  25 Apr 2001 
Last Modified:  26 Dec 2012 14:03 
Repository Staff Only: item control page