On the power of deterministic reductions to C=P

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 P [superA] P [super C=P super A] and BPP [super A] P [super C=P super A]. From this we can conclude that techniques that would prove that C=P and PP are polynomial-time Turing equivalent would not relativize.Postprint (published version