Standard

Refining the polynomial hierarchy. / Selivanov, V. L.

In: Algebra and Logic, Vol. 38, No. 4, 01.01.1999, p. 248-258.

Research output: Contribution to journal › Review article › peer-review

Harvard

Selivanov, VL 1999, 'Refining the polynomial hierarchy', Algebra and Logic, vol. 38, no. 4, pp. 248-258. https://doi.org/10.1007/BF02671730

APA

Selivanov, V. L. (1999). Refining the polynomial hierarchy. Algebra and Logic, 38(4), 248-258. https://doi.org/10.1007/BF02671730

Vancouver

Selivanov VL. Refining the polynomial hierarchy. Algebra and Logic. 1999 Jan 1;38(4):248-258. https://doi.org/10.1007/BF02671730

Author

Selivanov, V. L. / Refining the polynomial hierarchy. In: Algebra and Logic. 1999 ; Vol. 38, No. 4. pp. 248-258.

BibTeX

@article{08f4b4cc07ec48098e8f6c1d2d18938c,
title = "Refining the polynomial hierarchy",
abstract = "By a result of Kadin, the difference hierarchy over NP does not collapse if the polynomial hierarchy does not. We extend this result to a natural refinement of the polynomial hierarchy. The refinement is obtained from levels of the polynomial hierarchy by validly applying addition modulo 2, and so here we call it the plus-hierarchy. Also, we consider two refinements of the plus-hierarchy, which may be relevant to a classification of some languages. {\textcopyright} 1999 Kluwer Academic/Plenum Publishers.",
author = "Selivanov, {V. L.}",
year = "1999",
month = jan,
day = "1",
doi = "10.1007/BF02671730",
language = "English",
volume = "38",
pages = "248--258",
journal = "Algebra and Logic",
issn = "0002-5232",
publisher = "Springer Nature",
number = "4",

}

RIS

TY - JOUR

T1 - Refining the polynomial hierarchy

AU - Selivanov, V. L.

PY - 1999/1/1

Y1 - 1999/1/1

N2 - By a result of Kadin, the difference hierarchy over NP does not collapse if the polynomial hierarchy does not. We extend this result to a natural refinement of the polynomial hierarchy. The refinement is obtained from levels of the polynomial hierarchy by validly applying addition modulo 2, and so here we call it the plus-hierarchy. Also, we consider two refinements of the plus-hierarchy, which may be relevant to a classification of some languages. © 1999 Kluwer Academic/Plenum Publishers.

AB - By a result of Kadin, the difference hierarchy over NP does not collapse if the polynomial hierarchy does not. We extend this result to a natural refinement of the polynomial hierarchy. The refinement is obtained from levels of the polynomial hierarchy by validly applying addition modulo 2, and so here we call it the plus-hierarchy. Also, we consider two refinements of the plus-hierarchy, which may be relevant to a classification of some languages. © 1999 Kluwer Academic/Plenum Publishers.

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

U2 - 10.1007/BF02671730

DO - 10.1007/BF02671730

M3 - Review article

AN - SCOPUS:0010579734

VL - 38

SP - 248

EP - 258

JO - Algebra and Logic

JF - Algebra and Logic

SN - 0002-5232

IS - 4

ER -

ID: 127141277