On polynomial time Turing and many-one completeness in PSPACE
Osamu Watanabe, S. Tang · 2003
The different between polynomial-time-Turing- and polynomial-time-many-one-completeness notions in PSPACE is shown from each of the following assumptions: (i) a randomized completeness notion differs from a deterministic one in PSPACE; and (ii) PSPACE has a dense set, almost every element of which is hard to produce by any polynomial-time computation. A. Mayer and M. Paterson (Tech. Rep. MIT/LCS/TM-126, MIT, 1979) investigated polynomial-time-many-one-reducibility of PSPACE-complete sets to sparse sets. It is pointed out that their observation indicates the difference between the power of the latter and that of polynomial-time-Turing-reducibility. Machinery that uses this difference for separating the two kinds of completeness in PSPACE is established.>