Re: Complexity Theory for Simpletons


Woeginger Gerhard wrote:
Craig Feinstein <cafeinst@xxxxxxx> wrote:
# Roughly, I mean that algorithm A is "the best algorithm for solving
# subset-sum with respect to n on computer X" if the worst-case
# running-time of A for all subsets of size n on computer X is better
# than that of any other algorithm running on subsets of size n on
# computer X.

=======================
You write: ... for solving subset-sum "with repect to n"
on computer X

Does this mean: With respect to one particular value n?
(A is fast for subsets of size n; it might be slow for
subsets of other sizes).

Or does this mean: With respect to all numbers n?
(A is fast for subsets of size 1; and fast for subsets of size 2;
and fast for subsets of size 3; and so on.)

One particular value n, in the context of my definition.


=======================
You write: ... solving subset-sum with repect to n "on computer X"

Does this mean: On your laptop X? (This would be ridiculous. Your
laptop cannot even store an input for SUBSET-SUM with n=10^1000
integers.)

Which computer (or computer model) did you have in mind?


Certainly not a laptop for reasons that you pointed out. Just a
theoretical computer that can take arbitrarily large input. The
specifics of the model of computation are not necessary for the
argument in the paper to work.


--Gerhard


___________________________________________________________
Gerhard J. Woeginger http://www.win.tue.nl/~gwoegi/

.

Relevant Pages