Presentation | 2010-07-02 On the Relationship between Recognizing Languages and Computing Functions Shingo HASEGAWA, Shuji ISOBE, Hiroki SHIZUYA, |
---|---|
PDF Download Page | PDF download Page Link |
Abstract(in Japanese) | (See Japanese page) |
Abstract(in English) | We explore the relationship between the class NP and the function class NPMV_g, the set of witness functions for languages in NP. The relationship between NP and NPMVg is studied in the context of the self-computability of sets. In this paper, we consider slightly relaxed valiant of the self-computability and show the following two results for functions in NPMV_g with coNP domains: 1) for any function f in FewPF_g, f reduces an NP∩coNP language; and 2) any function f in NPMV_g reduces an NP∩coNP language only when NP = coNP. |
Keyword(in Japanese) | (See Japanese page) |
Keyword(in English) | multivalued function / NP / NPMV_g / self-computability |
Paper # | ISEC2010-37,SITE2010-33,ICSS2010-43 |
Date of Issue |
Conference Information | |
Committee | ICSS |
---|---|
Conference Date | 2010/6/24(1days) |
Place (in Japanese) | (See Japanese page) |
Place (in English) | |
Topics (in Japanese) | (See Japanese page) |
Topics (in English) | |
Chair | |
Vice Chair | |
Secretary | |
Assistant |
Paper Information | |
Registration To | Information and Communication System Security (ICSS) |
---|---|
Language | ENG |
Title (in Japanese) | (See Japanese page) |
Sub Title (in Japanese) | (See Japanese page) |
Title (in English) | On the Relationship between Recognizing Languages and Computing Functions |
Sub Title (in English) | |
Keyword(1) | multivalued function |
Keyword(2) | NP |
Keyword(3) | NPMV_g |
Keyword(4) | self-computability |
1st Author's Name | Shingo HASEGAWA |
1st Author's Affiliation | Graduate School of Information Sciences, Tohoku University() |
2nd Author's Name | Shuji ISOBE |
2nd Author's Affiliation | Graduate School of Information Sciences, Tohoku University |
3rd Author's Name | Hiroki SHIZUYA |
3rd Author's Affiliation | Graduate School of Information Sciences, Tohoku University |
Date | 2010-07-02 |
Paper # | ISEC2010-37,SITE2010-33,ICSS2010-43 |
Volume (vol) | vol.110 |
Number (no) | 115 |
Page | pp.pp.- |
#Pages | 6 |
Date of Issue |