Martingales and complexity theory

In this dissertation, we demonstrate three new techniques for applying martingale theory to computational complexity theory.;We present a new technique called the Generalized Reachability Method that uses martingale theory over a stochastic process for a computation on a specific input. This method proves that the accepting probability of certain classes of probabilistic computations is a submartingale and that the upper time complexity of the computation is a stopping time relative to this submartingale. We then present two applications of this method. First, we apply this method to interactive proof systems and give an alternative proof for an upper time bound of Lipton and Condon for constant space-bounded interactive proof systems. In applying our method to probabilistic Turing Machines, we present, an alternative proof of a critical lemma in Simon's result that space-bounded probabilistic complexity classes are closed under complementation.;We show a necessary condition for a distributional problem to be in Average-P in Levin's average-case complexity. We show that if a distributional problem is in Average-P, the running time of any deterministic algorithm that solves it is a uniformly integrable submartingle.;We offer a sufficient condition for when a stochastic process will visit a subset of its states infinitely often with probability one. This technique relies on martingale convergence theorems. We show that all left-oriented Markov chains, chains that are divided into levels such that the expected level of any state is strictly less than the level in which it exists, satisfy our sufficient condition. As an application of our sufficient condition, we present a sufficient condition for when a probabilistic computation will halt with probability one.;Finally, we point out open questions related to applying our techniques to broader classes of probabilistic computations and stochastic processes and to deriving a sufficient condition for Average-P.