Autoreducibility and Completeness for Partial Multivalued Functions

Shuji ISOBE  Eisuke KOIZUMI  

IEICE TRANSACTIONS on Information and Systems   Vol.E100-D   No.3   pp.422-427
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.