Reducibility, randomness, and intractibility (Abstract)
Leonard M. Adleman, Kenneth L. Manders · 1977
The method of showing a problem NP-complete by polynomial reduction is one of the most elegant and productive in our theory ([ 1 ], [ 3 ]). It is a means of providing compelling evidence that a problem in NP is not in P. In this paper we will demonstrate new methods for showing this.