Autoreducibility and completeness for partial multivalued functions

Shuji Isobe; Eisuke Koizumi

doi:10.1587/transinf.2016FCP0006

Autoreducibility and completeness for partial multivalued functions

Shuji Isobe, Eisuke Koizumi

Center for Data-driven Science and Artificial Intelligence (CDS)

Research output: Contribution to journal › Article › peer-review

Abstract

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.

Original language	English
Pages (from-to)	422-427
Number of pages	6
Journal	IEICE Transactions on Information and Systems
Volume	E100D
Issue number	3
DOIs	https://doi.org/10.1587/transinf.2016FCP0006
Publication status	Published - 2017 Mar

Keywords

Autoreduction
Many-one-like reduction
Partial multivalued function

Access to Document

10.1587/transinf.2016FCP0006

Cite this

@article{f08af5cef45f48558d3f328e8b96da8b,

title = "Autoreducibility and completeness for partial multivalued functions",

abstract = "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.",

keywords = "Autoreduction, Many-one-like reduction, Partial multivalued function",

author = "Shuji Isobe and Eisuke Koizumi",

note = "Publisher Copyright: {\textcopyright} 2017 The Institute of Electronics, Information and Communication Engineers.",

year = "2017",

month = mar,

doi = "10.1587/transinf.2016FCP0006",

language = "English",

volume = "E100D",

pages = "422--427",

journal = "IEICE Transactions on Information and Systems",

issn = "0916-8532",

publisher = "Maruzen Co., Ltd/Maruzen Kabushikikaisha",

number = "3",

}

TY - JOUR

T1 - Autoreducibility and completeness for partial multivalued functions

AU - Isobe, Shuji

AU - Koizumi, Eisuke

PY - 2017/3

Y1 - 2017/3

N2 - 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.

AB - 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.

KW - Autoreduction

KW - Many-one-like reduction

KW - Partial multivalued function

UR - http://www.scopus.com/inward/record.url?scp=85016107820&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85016107820&partnerID=8YFLogxK

U2 - 10.1587/transinf.2016FCP0006

DO - 10.1587/transinf.2016FCP0006

M3 - Article

AN - SCOPUS:85016107820

SN - 0916-8532

VL - E100D

SP - 422

EP - 427

JO - IEICE Transactions on Information and Systems

JF - IEICE Transactions on Information and Systems

IS - 3

ER -

Autoreducibility and completeness for partial multivalued functions

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this