
For FullText 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
Publication
IEICE TRANSACTIONS on Information and Systems
Vol.E100D
No.3
pp.422427 Publication Date: 2017/03/01
Online ISSN: 17451361 Type of Manuscript: Special Section PAPER (Special Section on Foundations of Computer Science — New Trends in Theoretical Computer Science —) Category: Keyword: partial multivalued function, autoreduction, manyonelike reduction,
Full Text: PDF(198.8KB) >>Buy this Article
Summary:
In this paper, we investigate a relationship between manyonelike autoreducibility and completeness for classes of functions computed by polynomialtime nondeterministic Turing transducers. We prove two results. One is that any manyone complete function for these classes is metric manyone autoreducible. The other is that any strict metric manyone complete function for these classes is strict metric manyone autoreducible.

