论文标题
通过语义的概率复杂性课程
Probabilistic Complexity Classes through Semantics
论文作者
论文摘要
在最近的一篇论文中，作者展示了如何使用线性逻辑的相互作用图模型来获得非确定性复杂性类别的隐式特征。在本文中，我们展示了这种隐式复杂性理论（ICC）的语义方法如何用于表征确定性和概率的计算模型。在此过程中，我们获得了小组动作与复杂性类别的确定性和概率层次结构之间的对应关系。作为一种特殊情况，我们提供了plogspace（未结合的误差概率对数空间）和pptime（无界错误概率概率多项式时间）的第一个隐式特征
In a recent paper, the author has shown how Interaction Graphs models for linear logic can be used to obtain implicit characterisations of non-deterministic complexity classes. In this paper, we show how this semantic approach to Implicit Complexity Theory (ICC) can be used to characterise deterministic and probabilistic models of computation. In doing so, we obtain correspondences between group actions and both deterministic and probabilistic hierarchies of complexity classes. As a particular case, we provide the first implicit characterisations of the classes PLogspace (un-bounded error probabilistic logarithmic space) and PPtime (unbounded error probabilistic polynomial time)
