0000000000174750

AUTHOR

Iain A. Stewart

showing 2 related works from this author

Positive Versions of Polynomial Time

1998

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.

Class (set theory)Computational complexity theoryAlgorithmic logicTheoretical Computer ScienceComputer Science ApplicationsCombinatoricsTuring machinesymbols.namesakeMonotone polygonNon-deterministic Turing machineComputational Theory and MathematicsComplexity classsymbolsTime complexityMathematicsInformation Systems
researchProduct

On positive P

2002

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.

Discrete mathematicsCombinatoricsClass (set theory)Monotone polygonBoolean circuitComplexity classVariety (universal algebra)Boolean functionTime complexitySubclassMathematicsProceedings of Computational Complexity (Formerly Structure in Complexity Theory)
researchProduct