6533b833fe1ef96bd129ca17
RESEARCH PRODUCT
On positive P
Iain A. StewartC. LautemannT. Schwenticksubject
Discrete mathematicsCombinatoricsClass (set theory)Monotone polygonBoolean circuitComplexity classVariety (universal algebra)Boolean functionTime complexitySubclassMathematicsdescription
Continuing a line of research opened up by Grigni and Sipser (1992) and further pursued by Stewart (1994), we show that a wide variety of equivalent characterizations of P still remain equivalent when restricted to be positive. All these restrictions thus define the same class posP, a proper subclass of monP, the class of monotone problems in P. We also exhibit complete problems for posP under very weak reductions.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 2002-12-23 | Proceedings of Computational Complexity (Formerly Structure in Complexity Theory) |