On the Length-Decreasing Self-Reducibility and the Many-One-Like Reducibilities 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 NPMVg)-complete function which is not length-decreasing self-reducible unless P=NP.
著者
-
Isobe Shuji
Department Of Computer And Mathematical Sciences Graduate School Of Information Sciences Tohoku Univ
-
Shizuya Hiroki
Department Of Computer And Mathematical Sciences Graduate School Of Information Sciences Tohoku Univ
-
Koizumi Eisuke
Department Of Computer And Mathematical Sciences The Graduate School Of Information Sciences Tohoku
-
HUH Ji-Won
Department of Computer and Mathematical Sciences, Graduate School of Information Sciences, Tohoku University
-
KOIZUMI Eisuke
Department of Computer and Mathematical Sciences, Graduate School of Information Sciences, Tohoku University
関連論文
- Yamato 980459: Mineralogy and petrology of a new shergottite-related rock from Antarctica
- NPMV-Complete Functions That Compute Discrete Logarithms and Integer Factorization
- On the Difficulty of Searching for a String without Decryption (Special Section on Cryptography and Information Security)
- Making Cryptographic Primitives Harder
- Toward Separating Integer Factoring from Discrete Logarithm mod p(Foundations,Cryptography and Information Security)
- On the Polynomial Time Computability of Abstract Ray-Tracing Problems(Discrete Mathematics and Its Applications)
- Mineralogy and petrology of Yamato 000593: Comparison with other Martian nakhlite meteorites
- Comparative mineralogy of magmatic inclusions in olivine from the Chassigny and Nakhla martian meteorites
- Origin of olivine megacrysts and the groundmass crystallization of the Dar al Gani 476 shergottite
- On the Length-Decreasing Self-Reducibility and the Many-One-Like Reducibilities for Partial Multivalued Functions
- On the Length-Decreasing Self-Reducibility and the Many-One-Like Reducibilities for Partial Multivalued Functions