A higher-order characterization of probabilistic polynomial time

作     者：Dal Lago, Ugo Toldin, Paolo Parisen 

作者机构：Univ Bologna Dipartimento Sci Informaz Equipe FOCUS INRIA Sophia Antipolis I-40127 Bologna Italy 

出 版 物：《INFORMATION AND COMPUTATION》 (信息与计算)

年 卷 期：2015年第241卷

页      面：114-141页

核心收录：

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 08[工学] 0701[理学-数学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：Implicit computational complexity Probabilistic classes 

摘      要：We present RSLR, an implicit higher-order characterization of the class PP of those problems which can be decided in probabilistic polynomial time with error probability smaller than 1/2. Analogously, a (less implicit) characterization of the class BPP can be obtained. RSLR is an extension of Hofmann s SLR with a probabilistic primitive, which enjoys basic properties such as subject reduction and confluence. Polynomial time soundness of RSLR is obtained by syntactical means, as opposed to the standard literature on SLR-derived systems, which use semantics in an essential way. (C) 2014 Elsevier Inc. All rights reserved.