Autoreducibility and Completeness for Partial Multivalued Functions
Shuji Isobe, Eisuke Koizumi · IEICE Transactions on Information and Systems · 2017
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.