On γ-reducibility versus polynomial time many-one reducibility(Extended Abstract)
Timothy J. Long · 1979
We prove that a class of functions (denoted by NPCPt), whose graphs can be accepted in non-deterministic polynomial time, can be evaluated in deterministic polynomial time if and only if γ-reducibility is equivalent to polynomial time many-one reducibility. We also modify the proof technique used to obtain part of this result to obtain the stronger result that if every γ-reduction can be replaced by a polynomial time Turing reduction then every function in NPCPt can be evaluated in deterministic polynomial time.