A decision problem that is Cook-reducible to its complement

Question

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.

Answer 1

Here's how to polynomial-time reduce an instance of the COMPOSITE decision problem to the PRIME decision problem.

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.