---
title: "Where the Really Hard Problems Are"
authors:
  - "Peter C. Cheeseman"
  - "Bob Kanefsky"
  - "William M. Taylor"
doi: ""
url: "https://ijcai.org/proceedings/1991/50"
pdf: "https://ijcai.org/proceedings/1991/0050.pdf"
venue: "Proceedings of the Twelfth International Joint Conference on Artificial Intelligence"
year: 1991
pages: "331-339"
track: "Automated Reasoning"
keywords:
---

# Where the Really Hard Problems Are

Peter C. Cheeseman, Bob Kanefsky, William M. Taylor

*Proceedings of the Twelfth International Joint Conference on Artificial Intelligence*, pages 331-339.

## 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 wellseparated 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.