Polynominal time reducibility
Richard E. Ladner · 1973
Several of the results that appear in [4] are stated to be true of polynominal time reducibility (≤p) but are not proved explicitly. We shall prove several of these results with the hope of shedding some light on the “determinism vs. nondeterminism” problem. The ideas behind these proofs already exist in [4] but appear here in a different setting. We shall spend most of our time on two theorems: (i) If φ <p Β then there exists an Α such that φ<p Α