For any two problems A and B, if A is in P(complexity) then A is reducible to B.
Could anyone explain why this is true?
For any two problems A and B, if A is in P(complexity) then A is reducible to B.
Could anyone explain why this is true?
I'll assume you're using this definition of reduction: $A$ is reducible to $B$ just if there exists a Turing machine running in time polynomial in the length of input that takes an instance $x$ of $A$ and halts with an instance $x'$ of $B$ such that $x\in L(A)$ if and only if $x' \in L(B)$, where $L(A), L(B)$ are the languages for which $A$ and $B$ are decision problems. This is the most standard defintion, but for precision should really be referred to as polynomial-time reducibility, which would probably have helped you out with the problem.
So, the problem statement being true depends on there being strings $y\in B$ and $y' \notin L(B)$ as long as there are strings both in and not in $L(A)$. If so, all we need to do is run a polynomial-time machine deciding whether $x \in L(A)$, then write $y$ at the end if $x \in L(A)$ and $y'$ if not. This last step only adds constant time, so it's certainly a polynomial reduction.