How do we show that $A$ is polynomial time reducible to itself?

324 Views Asked by At

How do we show that $A$ is polynomial time reducible to itself, i.e. that $A \le_p A$?

I know how to prove that it is transitive, but I don't know how to prove it's reflexive.

I'm aware that it's something along the lines of x is in A, so there's a function of A that is in A. Not sure how to continue!

1

There are 1 best solutions below

0
On

You can use the identity function. This clearly satisfies the definition of a reduction.