0000000000174751

AUTHOR

C. Lautemann

showing 3 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

Circuit Lower Bounds via Ehrenfeucht-Fraisse Games

2006

In this paper we prove that the class of functions expressible by first order formulas with only two variables coincides with the class of functions computable by AC/sup 0/ circuits with a linear number of gates. We then investigate the feasibility of using Ehrenfeucht-Fraisse games to prove lower bounds for that class of circuits, as well as for general AC/sup 0/ circuits.

CombinatoricsDiscrete mathematicsComputer Science::Hardware ArchitectureClass (set theory)Computer Science::Emerging TechnologiesComputabilityGame complexityEhrenfeucht–Fraïssé gameCircuit complexityGame theoryLinear numberElectronic circuitMathematics21st Annual IEEE Conference on Computational Complexity (CCC'06)
researchProduct