論文

査読有り
2017年3月

Autoreducibility and Completeness for Partial Multivalued Functions

IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS
  • Shuji Isobe
  • ,
  • Eisuke Koizumi

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.

リンク情報
DOI
https://doi.org/10.1587/transinf.2016FCP0006
Web of Science
https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcAuth=JSTA_CEL&SrcApp=J_Gate_JST&DestLinkType=FullRecord&KeyUT=WOS:000399371000003&DestApp=WOS_CPL
ID情報
  • DOI : 10.1587/transinf.2016FCP0006
  • ISSN : 1745-1361
  • Web of Science ID : WOS:000399371000003

エクスポート
BibTeX RIS