On the Length-Decreasing Self-Reducibility and the Many-One-Like Reducibilities for Partial Multivalued Functions

Ji-Won HUH; Shuji ISOBE; Eisuke KOIZUMI; Hiroki SHIZUYA

doi:10.1587/transinf.E96.D.465

On the Length-Decreasing Self-Reducibility and the Many-One-Like Reducibilities for Partial Multivalued Functions

Ji-Won HUH, Shuji ISOBE, Eisuke KOIZUMI, Hiroki SHIZUYA

Full Text Views

0

Share
Cite this

Summary :

In this paper, we investigate a relationship between the length-decreasing self-reducibility and the many-one-like reducibilities for partial multivalued functions. We show that if any parsimonious (many-one or metric many-one) complete function for NPMV (or NPMVg) is length-decreasing self-reducible, then any function in NPMV (or NPMVg) has a polynomial-time computable refinement. This result implies that there exists an NPMV (or NPMVg)-complete function which is not length-decreasing self-reducible unless P = NP.

Publication: IEICE TRANSACTIONS on Information Vol.E96-D No.3 pp.465-471

Publication Date: 2013/03/01

Publicized

Online ISSN: 1745-1361

DOI: 10.1587/transinf.E96.D.465

Type of Manuscript: Special Section PAPER (Special Section on Foundations of Computer Science — New Trends in Algorithms and Theory of Computation —)

Category

Cite this

Copy

Ji-Won HUH, Shuji ISOBE, Eisuke KOIZUMI, Hiroki SHIZUYA, "On the Length-Decreasing Self-Reducibility and the Many-One-Like Reducibilities for Partial Multivalued Functions" in IEICE TRANSACTIONS on Information, vol. E96-D, no. 3, pp. 465-471, March 2013, doi: 10.1587/transinf.E96.D.465.
Abstract: In this paper, we investigate a relationship between the length-decreasing self-reducibility and the many-one-like reducibilities for partial multivalued functions. We show that if any parsimonious (many-one or metric many-one) complete function for NPMV (or NPMVg) is length-decreasing self-reducible, then any function in NPMV (or NPMVg) has a polynomial-time computable refinement. This result implies that there exists an NPMV (or NPMVg)-complete function which is not length-decreasing self-reducible unless P = NP.
URL: https://globals.ieice.org/en_transactions/information/10.1587/transinf.E96.D.465/_p

Copy

@ARTICLE{e96-d_3_465,
author={Ji-Won HUH, Shuji ISOBE, Eisuke KOIZUMI, Hiroki SHIZUYA, },
journal={IEICE TRANSACTIONS on Information},
title={On the Length-Decreasing Self-Reducibility and the Many-One-Like Reducibilities for Partial Multivalued Functions},
year={2013},
volume={E96-D},
number={3},
pages={465-471},
abstract={In this paper, we investigate a relationship between the length-decreasing self-reducibility and the many-one-like reducibilities for partial multivalued functions. We show that if any parsimonious (many-one or metric many-one) complete function for NPMV (or NPMVg) is length-decreasing self-reducible, then any function in NPMV (or NPMVg) has a polynomial-time computable refinement. This result implies that there exists an NPMV (or NPMVg)-complete function which is not length-decreasing self-reducible unless P = NP.},
keywords={},
doi={10.1587/transinf.E96.D.465},
ISSN={1745-1361},
month={March},}

Copy

TY - JOUR
TI - On the Length-Decreasing Self-Reducibility and the Many-One-Like Reducibilities for Partial Multivalued Functions
T2 - IEICE TRANSACTIONS on Information
SP - 465
EP - 471
AU - Ji-Won HUH
AU - Shuji ISOBE
AU - Eisuke KOIZUMI
AU - Hiroki SHIZUYA
PY - 2013
DO - 10.1587/transinf.E96.D.465
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E96-D
IS - 3
JA - IEICE TRANSACTIONS on Information
Y1 - March 2013
AB - In this paper, we investigate a relationship between the length-decreasing self-reducibility and the many-one-like reducibilities for partial multivalued functions. We show that if any parsimonious (many-one or metric many-one) complete function for NPMV (or NPMVg) is length-decreasing self-reducible, then any function in NPMV (or NPMVg) has a polynomial-time computable refinement. This result implies that there exists an NPMV (or NPMVg)-complete function which is not length-decreasing self-reducible unless P = NP.
ER -