## 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.