6533b7d2fe1ef96bd125e30c
RESEARCH PRODUCT
Positive Versions of Polynomial Time
T. SchwentickIain A. StewartC. Lautemannsubject
Class (set theory)Computational complexity theoryAlgorithmic logicTheoretical Computer ScienceComputer Science ApplicationsCombinatoricsTuring machinesymbols.namesakeMonotone polygonNon-deterministic Turing machineComputational Theory and MathematicsComplexity classsymbolsTime complexityMathematicsInformation Systemsdescription
Abstract We show that restricting a number of characterizations of the complexity class P to be positive (in natural ways) results in the same class of (monotone) 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 exhibit complete problems for posP via weak logical reductions, as we do for other logically defined classes of problems. Our work is a continuation of research undertaken by Grigni and Sipser, and subsequently Stewart; indeed, we introduce the notion of a positive deterministic Turing machine and consequently solve a problem posed by Grigni and Sipser.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 1998-12-01 |