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.

  • 1
    $\begingroup$ 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. $\endgroup$ – marty cohen Mar 26 '15 at 20:49

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.