2017年3月
Autoreducibility and Completeness for Partial Multivalued Functions
IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS
- ,
- 巻
- E100D
- 号
- 3
- 開始ページ
- 422
- 終了ページ
- 427
- 記述言語
- 英語
- 掲載種別
- 研究論文(学術雑誌)
- DOI
- 10.1587/transinf.2016FCP0006
- 出版者・発行元
- IEICE-INST ELECTRONICS INFORMATION COMMUNICATIONS ENG
In this paper, we investigate a relationship between manyone-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 manyone complete function for these classes is strict metric many-one autoreducible.
- リンク情報
- ID情報
-
- DOI : 10.1587/transinf.2016FCP0006
- ISSN : 1745-1361
- Web of Science ID : WOS:000399371000003