Computer Science
On the power of deterministic reductions to C=P
Document Type
Article
Abstract
The counting class C=P, which captures the notion of "exact counting", while extremely powerful under various nondeterministic reductions, is quite weak under polynomial-time deterministic reductions. We discuss the analogies between NP and co-C=P, which allow us to derive many interesting results for such deterministic reductions to co-C=P. We exploit these results to obtain some interesting oracle separations. Most importantly, we show that there exists an oracle A such that {Mathematical expression} and {Mathematical expression} Therefore, techniques that would prove that C=P and PP are polynomial-time Turing equivalent, or that C=P is polynomial-time Turing hard for the polynomial-time hierarchy, would not relativize. © 1993 Springer-Verlag New York Inc.
Publication Title
Mathematical Systems Theory
Publication Date
1993
Volume
26
Issue
2
First Page
215
Last Page
233
ISSN
0025-5661
DOI
10.1007/BF01202284
Repository Citation
Green, Frederic, "On the power of deterministic reductions to C=P" (1993). Computer Science. 74.
https://commons.clarku.edu/faculty_computer_sciences/74
APA Citation
Green, F. (1993). On the power of deterministic reductions to C= P. Mathematical Systems Theory, 26(2), 215-233.