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

APA Citation

Green, F. (1993). On the power of deterministic reductions to C= P. Mathematical Systems Theory, 26(2), 215-233.

Link to Full Text

Share

COinS