Re: Reductions in P

t...@xxxxxxxxxxxxx wrote:

Not quite. Given what you've said so far, it is possible that g might
take an input of size m and generate an output of size as big as m^2.
This output will become the input for A3, which runs in time proportional
to the 4th power of the size m^2 of *its* input. Since (m^2)^4 = m^8,
the compound algorithm may take as long as the 8th power of the size m
of the original input.

Let' see. You're saying that g can take an input of size m and generate
output of size O(n^k), k in N. Ooops.

Well this didn't occur to me, since I have been studying time
complexity so far, but what are you basically talking about now, is
space complexity.

So this leads me to the following question: g() being polytime, what is
the worst space complexity for g? O(m^k)? Or can it be something like
O(e^m)?

Also if space complexity for g is O(m^k), does this mean that the
solution for p3 is O(m^k)*O(n^4) = O(m^k * n^4)? Thanks.

.