کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
428650 | 686852 | 2011 | 4 صفحه PDF | دانلود رایگان |
Let DD be a set of many-one degrees of disjoint NP-pairs. We define a proof system representation of DD to be a set of propositional proof systems PP such that each degree in DD contains the canonical NP-pair of a corresponding proof system in PP and the degree structure of DD is reflected by the simulation order among the corresponding proof systems in PP. We also define a nesting representation of DD to be a set of NP-pairs SS such that each degree in DD contains a representative NP-pair in SS and the degree structure of DD is reflected by the inclusion relations among their representative NP-pairs in SS. We show that proof system and nesting representations both exist for DD if the lower span of each degree in DD overlaps with DD on a finite set only. In particular, a linear chain of many-one degrees of NP-pairs has both a proof system representation and a nesting representation. This extends a result by Glaßer et al. (2009). We also show that in general DD has a proof system representation if it has a nesting representation where all representative NP-pairs share the same set as their first components.
Research highlights
► We define proof systems and nesting representations of degrees of NP-pairs.
► Both representations exist for certain nontrivial collections of degrees of NP-pairs.
► A special type of nesting representations yield proof system representations.
Journal: Information Processing Letters - Volume 111, Issue 7, 1 March 2011, Pages 348–351