# A decision problem that is Cook-reducible to its complement

I'm taking an algorithms course and we are covering polynomial time reductions, and I've read online that many decision problems are polynomial-time reducible to their complements.

Can anyone give me an example of one such decision problem?

I tried to reduce the Composite decision problem to Prime, but don't really know how to go about it.

• I did a Google search for "decision problems are polynomial-time reducible to their complements" and got a number of hits. Some of them look promising. – marty cohen Mar 26 '15 at 20:49

1. Consider an instance of COMPOSITE in the form of a number $n$.
2. In polynomial time, determine if $n$ is prime (using the AKS algorithm).
3. If $n$ is prime, let $m = 4$, otherwise let $m = 2$.
4. $m$ is the corresponding instance of PRIME.