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

摘要

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 NPMV_g)-complete function which is not length-decreasing self-reducible unless P = NP.