Monotone Complexity

Summary

Abstract

We give a general complexity classification scheme for monotone computation, including monotone space-bounded and Turing machine models not previously considered. We propose monotone complexity classes including mACⁱ, mNCⁱ, mLOGCFL, mBWBP, mL, mNL, mP, mBPP and mNP. We define a simple notion of monotone reducibility and exhibit complete problems. This provides a framework for stating existing results and asking new questions.

We show that mNL (monotone nondeterministic log-space) is not closed under complementation, in contrast to Immerman's and Szelepcsényi's nonmonotone result [Imm88, Sze87] that NL = co-NL; this is a simple extension of the monotone circuit depth lower bound of Karchmer and Wigderson [KW90] for st-connectivity.

We also consider mBWBP (monotone bounded width branching programs) and study the question of whether mBWBP is properly contained in mNC¹, motivated by Barrington's result [Bar89] that BWBP = NC¹. Although we cannot answer this question, we show two preliminary results: every monotone branching program for majority has size Ω(n²) with no width restriction, and no monotone analogue of Barrington's gadget exists.

Introduction

A computation is monotone if it does not use the negation operation. Monotone circuits and formulas have been studied as restricted models of computation with the goal of developing techniques for the general problem of proving lower bounds.

In this paper we seek to unify the theory of monotone complexity along the lines of Babai, Frankl, and Simon who gave a framework for communication complexity theory. We propose a collection of monotone complexity models paralleling the familiar nonmonotone models. This provides a rich classification system for monotone functions including most monotone circuit classes previously considered, as well as monotone space-bounded complexity classes which have previously received little attention.