Positive versions of polynomial time

We show that restricting a number of characterizations of the complexity cl ass P to be positive (in natural ways) results in the same class of (monoto ne) problems, which we denote by posP. By a well-known result of Razborov, posP is a proper subclass of the class of monotone problems in P, We exhibi t complete problems for posP via weak logical reductions, as we do for othe r logically defined classes of problems. Our work is a continuation of rese arch undertaken by Grigni and Sipser, and subsequently Stewart; indeed, we introduce the notion of a positive deterministic Turing machine and consequ ently solve a problem posed by Grigni and Sipser. (C) 1998 Academic Press.