How would I create a polytime mapping reduction to prove A ≤p A for any language A.

I was thinking to assume A is in P to start. For every 𝑥: 𝑥∈𝐴 iff 𝑓(𝑥)∈𝐴.

But I am not sure what to do from there, any advice? I don't get how to show that you can polytime reduce a function to itself, because if you assume A has a Turing machine and a polytime decider, a function that is a polytime mapper, then how do you show its equal to each other?

  • $\begingroup$ I don't understand your confusion. What do you mean by "A has a Turing machine"? $\endgroup$
    – xskxzr
    Commented Nov 10, 2021 at 2:45

1 Answer 1


You need to construct a polytime function $f$ with the following property:

For every $x$: $x \in A$ iff $f(x) \in A$.

You take it from here.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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