On the probabilistic closure of the loose unambiguous hierarchy

作     者：Hirsch, Edward A. Sokolov, Dmitry 

作者机构：Russian Acad Sci Steklov Inst Math St Petersburg St Petersburg 191023 Russia 

出 版 物：《INFORMATION PROCESSING LETTERS》 (信息处理快报)

年 卷 期：2015年第115卷第9期

页      面：725-730页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：Government of the Russian Federation [14.Z50.31.0030] 

主　　题：Computational complexity Randomized algorithms Unambiguous computations Toda's theorem 

摘      要：Unambiguous hierarchies [1-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. 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 subset of BP . circle plus DP subset of P-PP can be strengthened to PH = BP . prUH., that is, the closure of our hierarchy under Schoning s BP operator equals the polynomial hierarchy. It is easily seen that BP . prUH. subset of BP . circle plus 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. (C) 2015 Elsevier B.V. All rights reserved.