Immunity and Simplicity for Exact Counting and Other Counting Classes

Issue		RAIRO-Theor. Inf. Appl. Volume 33, Number 2, March-April 1999


Page(s)		159 - 176
DOI		10.1051/ita:1999100

DOI: 10.1051/ita:1999100

Theoret. Informatics Appl. 33 (1999) 159-176

Immunity and Simplicity for Exact Counting and Other Counting Classes

J. Rothe
Institut für Informatik, Friedrich-Schiller-Universität Jena, 07740 Jena, Germany; (rothe@informatik.uni-jena.de)

Received January, 1998. Accepted March, 1999.

Abstract: Ko [26] and Bruschi [11] independently showed that, in some relativized world, PSPACE (in fact, ${\rm \oplus P}$ ) contains a set that is immune to the polynomial hierarchy (PH). In this paper, we study and settle the question of relativized separations with immunity for PH and the counting classes ${\rm PP}$ , ${\rm C\!\!\!\!=\!\!\!P}$ , and ${\rm \oplus P}$ in all possible pairwise combinations. Our main result is that there is an oracle A relative to which ${\rm C\!\!\!\!=\!\!\!P}$ contains a set that is immune to ${\rm BPP}^{{\rm \oplus P}}$ .In particular, this ${\rm C\!\!\!\!=\!\!\!P}^A$ set is immune to ${\rm PH}^A$ and to ${\rm \oplus P}^A$ . Strengthening results of Torán [48] and Green [18], we also show that, in suitable relativizations, NP contains a ${\rm C\!\!\!\!=\!\!\!P}$ -immune set, and ${\rm \oplus P}$ contains a ${\rm PP}^{{\rm PH}}$ -immune set. This implies the existence of a ${\rm C\!\!\!\!=\!\!\!P}^B$ -simple set for some oracle B, which extends results of Balcázar et al. [2,4]. Our proof technique requires a circuit lower bound for "exact counting'' that is derived from Razborov's [35] circuit lower bound for majority.

Keywords and phrases: Computational complexity, immunity, counting classes, relativized computation, circuit lower bounds.

AMS Subject Classification: 68Q15, 68Q10, 03D15

Communicated by: J. Gabarró.

What is OpenURL?

The OpenURL standard is a protocol for transmission of metadata describing the resource that you wish to access. An OpenURL link contains article metadata and directs it to the OpenURL server of your choice. The OpenURL server can provide access to the resource and also offer complementary services (specific search engine, export of references...). The OpenURL link can be generated by different means.

If your librarian has set up your subscription with an OpenURL resolver, OpenURL links appear automatically on the abstract pages.
You can define your own OpenURL resolver with your EDPS Account. In this case your choice will be given priority over that of your library.
You can use an add-on for your browser (Firefox or I.E.) to display OpenURL links on a page (see http://www.openly.com/openurlref/). You should disable this module if you wish to use the OpenURL server that you or your library have defined.