کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
427115 | 686448 | 2015 | 6 صفحه PDF | دانلود رایگان |
• We introduce a new version prUH
• prUH
• of the unambiguous hierarchy of promise problems.
• We prove that PH=BP⋅prUH
• PH=BP⋅prUH
• .
• Our result strengthens the first part of Toda's theorem PH⊆BP⋅⊕P⊆PPPPH⊆BP⋅⊕P⊆PPP, as BP⋅prUH
• ⊆BP⋅⊕PBP⋅prUH
• ⊆BP⋅⊕P.
Unambiguous hierarchies [1], [2] and [3] are defined similarly to the polynomial hierarchy; however, all witnesses must be unique. These hierarchies have subtle differences in the mode of using oracles. We consider a “loose” unambiguous hierarchy prUH
• prUH
• with relaxed definition of oracle access to promise problems. Namely, we allow to make queries that miss the promise set; however, the oracle answer in this case can be arbitrary (a similar definition of oracle access has been used in [4]).In this short note we prove that the first part of Toda's theorem PH⊆BP⋅⊕P⊆PPPPH⊆BP⋅⊕P⊆PPP can be strengthened to PH=BP⋅prUH
• PH=BP⋅prUH
• , that is, the closure of our hierarchy under Schöning's BP operator equals the polynomial hierarchy. It is easily seen that BP⋅prUH
• ⊆BP⋅⊕PBP⋅prUH
• ⊆BP⋅⊕P.The proof follows the same lines as Toda's proof, so the main contribution of the present note is a new definition that allows to characterize PH as a probabilistic closure of unambiguous computations.
Journal: Information Processing Letters - Volume 115, Issue 9, September 2015, Pages 725–730