Probabilistic Complexity Classes 1
Alejandro López-Ortíz · 1991
The purpose of this work is to present an overview of the class of problems solvable in probabilistic polynomial time with double sided error (PP ). We explore the relationship of PP to other complexity classes, in particular NP and the polynomial hierarchy, and discuss closure under some standard operations such as intersection and complementation. New proofs are given of some results from the literature using techniques developed by the author. ii Acknowledgements Several people made possible the successful completion of this work. Express thanks must be given to some of them. ffl To my girlfriend, Claudia Iturriaga Vel'azquez, for her unconditional love. ffl To Prabhakar Ragde. His patience towards my uncommon research style which, in particular, comprises exponentially many queries and interruptions is praised. ffl To all my friends, for cheering me up during hard times. Particular thanks to Vladimir Estivill-Castro and Luke O'Connor. Lastly, financial support from the Institut...