Examination of A Boundary Between P and NP-Complete Problem,
Abstract
Since the introduction of the notion of NP-completeness in the study of complexity theory about ten years ago, there has been an explosion of research activities in the area. In particular, the collective effort of many researchers has led to the discovery of a very large number of problems that are certified to be NP-complete. However, there is an interesting question about which very little is known, namely, what makes a problem NP-complete? IN order to gain further insight into the characterization of NP-complete problems, we studied several problem areas in which there is a spectrum of problems whose complexities vary with some 'small' variations on the assumptions. We hope that a further understanding of the 'boundary' that separates those problems in P and those problems that are NP-complete will lead to a further understanding of the characterization of NP-complete problems.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jan 01, 1980
- Accession Number
- ADA102231
Entities
People
- J. R. Egan
Organizations
- University of Illinois Urbana–Champaign