DocumentCode
2517416
Title
On polynomial time Turing and many-one completeness in PSPACE
Author
Watanabe, Osamu ; TANG, Shouwen
Author_Institution
Dept. of Comput. Sci., Tokyo Inst. of Technol., Japan
fYear
1989
fDate
19-22 Jun 1989
Firstpage
15
Lastpage
23
Abstract
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
Keywords
Turing machines; computational complexity; PSPACE; Turing reducibility; completeness notion; polynomial time Turing; sparse sets; Density measurement; Length measurement; Mathematics; Polynomials;
fLanguage
English
Publisher
ieee
Conference_Titel
Structure in Complexity Theory Conference, 1989. Proceedings., Fourth Annual
Conference_Location
Eugene, OR
Print_ISBN
0-8186-1958-9
Type
conf
DOI
10.1109/SCT.1989.41810
Filename
41810
Link To Document