Name
Abstract | ||
|---|---|---|
It is well known that for many NP-complete problems, such as K-Sat, etc., typical cases are easy to solve; so that computationally hard cases must be rare (assuming P = NP). This paper shows that NP-complete problems can be summarized by at least one "order parameter", and that the hard problems occur at a critical value of such a parameter. This critical value separates two regions of characteristically different properties. For example, for K-colorability, the critical value separates overconstrained from underconstrained random graphs, and it marks the value at which the probability of a solution changes abruptly from near 0 to near 1. It is the high density of well-separated almost solutions (local minima) at this boundary that cause search algorithms to "thrash". This boundary is a type of phase transition and we show that it is preserved under mappings between problems. We show that for some P problems either there is no phase transition or it occurs for bounded N (and so bounds the cost). These results suggest a way of deciding if a problem is in P or NP and why they are different. |
Year | Venue | Keywords |
|---|---|---|
1991 | IJCAI | bounded n,p problem,hard problem,different property,computationally hard case,cause search algorithm,critical value,phase transition,np-complete problem,order parameter,local minima,random graph,np complete problem,search algorithm |
Field | DocType | ISBN |
Discrete mathematics,Combinatorics,Search algorithm,Random graph,Phase transition,High density,Critical value,Maxima and minima,Mathematics,Bounded function | Conference | 1-55860-160-0 |
Citations | PageRank | References |
571 | 67.02 | 6 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Peter Cheeseman | 1 | 1523 | 557.85 |
| Bob Kanefsky | 2 | 685 | 73.79 |
| William M. Taylor | 3 | 571 | 67.02 |