Re: Reductions in P

In article <1152994284.349594.15480@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,
<ahuznot@xxxxxxxxx> wrote:
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.

Again, not exactly. What is relevant for the problem of composing
reductions is the *size of the output*. The size of the output is certainly
a lower bound on the space complexity, and also on the time complexity
(because each symbol of the output takes at least one unit of time to
print out), but the space complexity refers to how much space is used during
the entire course of the algorithm, and in general this could be much larger
than the size of the output.

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)?

You should be able to answer this question yourself using the observation
that one can access at most one unit of space during any single unit of
time.

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.

When you are *composing* the algorithms (i.e., taking the output of one and
feeding it into the other), you should usually be *composing* the functions
in question.
--
Tim Chow tchow-at-alum-dot-mit-dot-edu
The range of our projectiles---even ... the artillery---however great, will
never exceed four of those miles of which as many thousand separate us from
the center of the earth. ---Galileo, Dialogues Concerning Two New Sciences
.

Relevant Pages

  • Re: Protein folding and P = NP
    ... >space complexity of the protein folding problem as a function of the number ... then we would have a P algorithm for an empirically NP ... physics, a time-dependent solution is a constructive search algorithm. ...
    (comp.theory)
  • Re: How to transpose a matrix?
    ... >> than create a new matrix which is the transpose of the original matrix. ... >available for a piece of software that makes use of that algorithm has ... additional space complexity (for example, ... >sequential way without linear-space or worse buffering of output. ...
    (comp.lang.java.help)
  • Re: How to transpose a matrix?
    ... > than create a new matrix which is the transpose of the original matrix. ... it makes no logical sense to talk about space ... available for a piece of software that makes use of that algorithm has ... It DOES make sense to give space complexity of better than Oif the ...
    (comp.lang.java.help)