Deprecated: Function split() is deprecated in /srv/www/htdocs-cs/cie08/db-code.php on line 107

Deprecated: Function split() is deprecated in /srv/www/htdocs-cs/cie08/db-code.php on line 117
CiE 2008 - Regular Talk: - The Shrinking Property for NP and coNP
Computability in Europe 2008
Logic and Theory of Algorithms

Print current page  Print this page

Regular Talk:
The Shrinking Property for NP and coNP

Edit abstract data


Notice: Use of undefined constant session - assumed 'session' in /srv/www/htdocs-cs/cie08/conf-code.php on line 440

Notice: Use of undefined constant slot - assumed 'slot' in /srv/www/htdocs-cs/cie08/conf-code.php on line 441

Notice: Use of undefined constant room - assumed 'room' in /srv/www/htdocs-cs/cie08/conf-code.php on line 442
Speaker: Christian Glaßer
Author(s): Christian Glaßer, Christian Reitwießner and Victor Selivanov
Slot: Wed, 17:30-17:50, Room 20 (col. 1)

Abstract

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 and coNP do not have the shrinking property, unless PH is finite. In
general, Sigma_n and Pi_n do not have the shrinking property, unless PH is
finite. This solves an open question from [Selivanov 94].

2. The separation property does not hold for NP, unless UP \subseteq coNP.

3. The shrinking property does not hold for NP, unless there exist NP-hard
disjoint NP-pairs (existence of such pairs would contradict a conjecture
by Even, Selman, and Yacobi).

4. The shrinking property does not hold for NP, unless there exist
complete disjoint NP-pairs.

Moreover, we prove that the assumption NP \neq coNP is too weak to refute
the shrinking property for NP in a relativizable way. For this we
construct an oracle relative to which P = NP \cap coNP, NP \neq coNP, and
NP has the shrinking property. This solves an open question by Blass and
Gurevich who explicitly ask for such an oracle.

websites: Arnold Beckmann
Warning: date(): It is not safe to rely on the system's timezone settings. You are *required* to use the date.timezone setting or the date_default_timezone_set() function. In case you used any of those methods and you are still getting this warning, you most likely misspelled the timezone identifier. We selected the timezone 'UTC' for now, but please set date.timezone to select your timezone. in /srv/www/htdocs-cs/cie08/conf-code.php on line 136
2008-05-31 Valid HTML 4.01! Valid CSS!