Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Victor Selivanov:

TR08-029 | 7th January 2008
Christian Glaßer, Christian Reitwießner, Victor Selivanov

The Shrinking Property for NP and coNP

We study the shrinking and separation properties (two notions well-known in descriptive set theory) for NP and coNP and show that under reasonable complexity-theoretic assumptions, both properties do not hold for NP and the shrinking property does not hold for coNP. In particular we obtain the following results.

1. NP ... more >>>

TR07-094 | 3rd August 2007
Christian Glaßer, Heinz Schmitz, Victor Selivanov

Efficient Algorithms for Membership in Boolean Hierarchies of Regular Languages

The purpose of this paper is to provide efficient algorithms that decide membership for classes of several Boolean hierarchies for which efficiency (or even decidability) were previously not known. We develop new forbidden-chain characterizations for the single levels of these hierarchies and obtain the following results:

1. The classes of ... more >>>

ISSN 1433-8092 | Imprint