Standard

The shrinking property for NP and coNP. / Glaßer, Christian; Reitwießner, Christian; Selivanov, Victor.

In: Theoretical Computer Science, Vol. 412, No. 8-10, 04.03.2011, p. 853-864.

Research output: Contribution to journal › Article › peer-review

Harvard

Glaßer, C, Reitwießner, C & Selivanov, V 2011, 'The shrinking property for NP and coNP', Theoretical Computer Science, vol. 412, no. 8-10, pp. 853-864. https://doi.org/10.1016/j.tcs.2010.11.035

APA

Glaßer, C., Reitwießner, C., & Selivanov, V. (2011). The shrinking property for NP and coNP. Theoretical Computer Science, 412(8-10), 853-864. https://doi.org/10.1016/j.tcs.2010.11.035

Vancouver

Glaßer C, Reitwießner C, Selivanov V. The shrinking property for NP and coNP. Theoretical Computer Science. 2011 Mar 4;412(8-10):853-864. https://doi.org/10.1016/j.tcs.2010.11.035

Author

Glaßer, Christian ; Reitwießner, Christian ; Selivanov, Victor. / The shrinking property for NP and coNP. In: Theoretical Computer Science. 2011 ; Vol. 412, No. 8-10. pp. 853-864.

BibTeX

@article{d12e4afdd5b64c92b09e5f5468768c3e,
title = "The shrinking property for NP and coNP",
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. NP and coNP do not have the shrinking property unless PH is finite. In general, ΣnP and ΠnP do not have the shrinking property unless PH is finite. This solves an open question posed by Selivanov (1994) [33].The separation property does not hold for NP unless UP⊆coNP.The shrinking property does not hold for NP unless there exist NP-hard disjoint NP-pairs (existence of such pairs would contradict a conjecture of Even et al. (1984) [6]).The shrinking property does not hold for NP unless there exist complete disjoint NP-pairs. Moreover, we prove that the assumption NP≠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∩coNP, NP≠coNP, and NP has the shrinking property. This solves an open question posed by Blass and Gurevich (1984) [3] who explicitly ask for such an oracle.{\textcopyright} 2010 Elsevier B.V. All rights reserved.",
keywords = "Computational complexity, Multivalued functions, NP-pairs, P-separability, Polynomial hierarchy",
author = "Christian Gla{\ss}er and Christian Reitwie{\ss}ner and Victor Selivanov",
year = "2011",
month = mar,
day = "4",
doi = "10.1016/j.tcs.2010.11.035",
language = "English",
volume = "412",
pages = "853--864",
journal = "Theoretical Computer Science",
issn = "0304-3975",
publisher = "Elsevier",
number = "8-10",

}

RIS

TY - JOUR

T1 - The shrinking property for NP and coNP

AU - Glaßer, Christian

AU - Reitwießner, Christian

AU - Selivanov, Victor

PY - 2011/3/4

Y1 - 2011/3/4

N2 - 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. NP and coNP do not have the shrinking property unless PH is finite. In general, ΣnP and ΠnP do not have the shrinking property unless PH is finite. This solves an open question posed by Selivanov (1994) [33].The separation property does not hold for NP unless UP⊆coNP.The shrinking property does not hold for NP unless there exist NP-hard disjoint NP-pairs (existence of such pairs would contradict a conjecture of Even et al. (1984) [6]).The shrinking property does not hold for NP unless there exist complete disjoint NP-pairs. Moreover, we prove that the assumption NP≠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∩coNP, NP≠coNP, and NP has the shrinking property. This solves an open question posed by Blass and Gurevich (1984) [3] who explicitly ask for such an oracle.© 2010 Elsevier B.V. All rights reserved.

AB - 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. NP and coNP do not have the shrinking property unless PH is finite. In general, ΣnP and ΠnP do not have the shrinking property unless PH is finite. This solves an open question posed by Selivanov (1994) [33].The separation property does not hold for NP unless UP⊆coNP.The shrinking property does not hold for NP unless there exist NP-hard disjoint NP-pairs (existence of such pairs would contradict a conjecture of Even et al. (1984) [6]).The shrinking property does not hold for NP unless there exist complete disjoint NP-pairs. Moreover, we prove that the assumption NP≠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∩coNP, NP≠coNP, and NP has the shrinking property. This solves an open question posed by Blass and Gurevich (1984) [3] who explicitly ask for such an oracle.© 2010 Elsevier B.V. All rights reserved.

KW - Computational complexity

KW - Multivalued functions

KW - NP-pairs

KW - P-separability

KW - Polynomial hierarchy

UR - http://www.scopus.com/inward/record.url?scp=79151476008&partnerID=8YFLogxK

U2 - 10.1016/j.tcs.2010.11.035

DO - 10.1016/j.tcs.2010.11.035

M3 - Article

AN - SCOPUS:79151476008

VL - 412

SP - 853

EP - 864

JO - Theoretical Computer Science

JF - Theoretical Computer Science

SN - 0304-3975

IS - 8-10

ER -

ID: 127086056