A polytime complexity analyser for Probabilistic Polynomial Time over imperative stack programs

2013/04/11 by Jean-Yves Moyen, Moyen, Jean-Yves, Paolo Parisen Toldin +1
Computer Science · #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Logic in Computer Science (cs.LO) #cs.CC #cs.LO

paper · pdf · doi:10.48550/arxiv.1304.3249

arxiv created 2013/04/11 · arxiv updated 2013/04/12

Abstract

We present iSAPP (Imperative Static Analyser for Probabilistic Polynomial Time), a complexity verifier tool that is sound and extensionally complete for the Probabilistic Polynomial Time (PP) complexity class. iSAPP works on an imperative programming language for stack machines. The certificate of polynomiality can be built in polytime, with respect to the number of stacks used.

Related

• An Higher-Order Characterization of Probabilistic Polynomial Time (Long Version)
• Pseudodeterministic Algorithms and the Structure of Probabilistic Time
• Computational Complexity of Probabilistic Turing Machines
• Hybrid Probabilistic Programs: Algorithms and Complexity
• On the Efficiency of Deciding Probabilistic Automata Weak Bisimulation