Structure in monotone complexity
Michelangelo Grigni, Michael Sipser · 1991
In this work we study complexity classes in monotone computation. Our main contributions are the following: ffl A consistent framework for monotone computation, including monotone analogues of many standard computational models. We define monotone simulations, and show that many (but not all) of the familiar simulations from general complexity theory are in fact monotone. ffl The search for provably non-monotone simulations as a research goal in monotone complexity. Our new example is the following: the simulation techniques of Immerman and Szelepcs'enyi are provably non-monotone, since we can separate mNL (monotone nondeterministic logarithmic space) from co-mNL. ffl Another separation: mL (monotone logarithmic space) is strictly stronger than mNC 1 (monotone polynomial size formulas). This may be seen as a strictly stronger application of the communication game technique introduced by Karchmer and Wigderson. Thesis Supervisor: Michael Sipser Title: Professor 4 Acknowledgmen...