For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Autoreducibility and Completeness for Partial Multivalued Functions
Shuji ISOBE Eisuke KOIZUMI
IEICE TRANSACTIONS on Information and Systems
Publication Date: 2017/03/01
Online ISSN: 1745-1361
Type of Manuscript: Special Section PAPER (Special Section on Foundations of Computer Science — New Trends in Theoretical Computer Science —)
partial multivalued function, autoreduction, many-one-like reduction,
Full Text: PDF(198.8KB)
>>Buy this Article
In this paper, we investigate a relationship between many-one-like autoreducibility and completeness for classes of functions computed by polynomial-time nondeterministic Turing transducers. We prove two results. One is that any many-one complete function for these classes is metric many-one autoreducible. The other is that any strict metric many-one complete function for these classes is strict metric many-one autoreducible.