DocumentCode
2115708
Title
On positive P
Author
Lautemann, Clemens ; Schwentick, Thomas ; Stewart, Iain A.
Author_Institution
Johannes Gutenberg Univ., Mainz, Germany
fYear
1996
fDate
24-27 May 1996
Firstpage
162
Lastpage
170
Abstract
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
Keywords
Turing machines; computational complexity; equivalence classes; formal logic; Boolean circuits; Turing machines; branching programs; complexity classes; equivalent characterizations; first-order logic; monotone Boolean function; monotone problems; positive P; very weak reductions; Automata; Boolean functions; Circuit stability; Logic circuits; Polynomials; Turing machines;
fLanguage
English
Publisher
ieee
Conference_Titel
Computational Complexity, 1996. Proceedings., Eleventh Annual IEEE Conference on
Conference_Location
Philadelphia, PA
Print_ISBN
0-8186-7386-9
Type
conf
DOI
10.1109/CCC.1996.507678
Filename
507678
Link To Document