Reducibility, randomness, and intractibility (Abstract)

Abstract

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.