Prev: HEAP SORT
Next: Greedy Algorithm
From: Woeginger Gerhard on 29 Mar 2006 02:45
Craig Feinstein <cafeinst(a)msn.com> wrote:
# You make a good point, Gerhard. In my paper, I am excluding non-uniform
# algorithms from consideration for obvious reasons.

Now we are back at the start.

If you are excluding non-uniform algorithms, then how do you define
your notion of "best" algorithm?

In the non-uniform case, you could define it as a kind of point-wise
optimal algorithm. But you are excluding this now "for obvious reasons".

In the uniform case, I do not think that something like a "best"
algorithm exists. So I guess that your paper is just dealing
with non-existing objects, and you cannot draw any conlcusions
from it.

--Gerhard


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

From: Bryan Olson on 29 Mar 2006 21:10
Woeginger Gerhard wrote:
[...]
> We know several models of computation, in which P=NP holds.

I don't think that's really right. The model is part of the
definitions of P and NP. Either P=NP or it doesn't.

Certainly we know of models in which all languages in NP are
decidable in poly-time, and that's enough to support your
case here.


--
--Bryan
From: tchow on 30 Mar 2006 12:53
In article <p6HWf.64589$dW3.27960(a)newssvr21.news.prodigy.com>,
Bryan Olson <fakeaddress(a)nowhere.org> wrote:
>Woeginger Gerhard wrote:
>[...]
>> We know several models of computation, in which P=NP holds.
>
>I don't think that's really right. The model is part of the
>definitions of P and NP. Either P=NP or it doesn't.

Well, this is just a quibble, isn't it? We can read "P" to mean "problems
solvable in deterministic polynomial time" and "NP" to mean "problems
solvable in nondeterministic polynomial time," where the model of
computation is implicit and can vary.
--
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
From: Craig Feinstein on 30 Mar 2006 22:34
Let me say it another way. In my paper, my model of computation is a
person named Mabel who works as a computer in the 1930's. I'm assuming
that Mabel lives forever, never gets tired of working, and never slows
down with age. (I also deal with another computer named Mildred also
working back then in the 1930's.) As you probably know, computers back
then were people. Nobody had the fancy definitions for models of
computation back then that we have today. Sometimes these fancy
definitions can really lead a person to see only trees but not see the
forest.

Suppose that Mabel were given the Meyer auf der Heide algorithm to
solve subset-sum. Do you really believe the propaganda that you have
been fed from the "Computer Science Establishment" (don't worry, I'm
only joking and not claiming that there is a real conspiracy except for
Microsoft) that Mabel is going to work in polynomial time with such an
algorithm?

For input n=1000, do you really believe that it's going to take Mabel
only 1000^16 time to do such a calculation? The code of such a
nonuniform algorithm increases in size exponentially with n, so Mabel
would not even be able to stay in her "computer room" when n=1000. She
would have to have much more than trillions of pages of instructions to
implement such an algorithm and would have to travel around quite a bit
to read the code. Essentially, just because the computer scientists say
this algorithm runs in polynomial time, if you apply it in real life,
it's going to still be exponential time.

The P vs. NP question is a question which applies to people like Mabel
and Mildred, not some crazily defined model of computation cooked up by
some computer scientist. That's why it's a good question and why I
worked on it.

Craig

From: Bryan Olson on 31 Mar 2006 02:38
tchow(a)lsa.umich.edu wrote:
> Bryan Olson wrote:
>
>>Woeginger Gerhard wrote:
>>[...]
>>
>>>We know several models of computation, in which P=NP holds.
>>
>>I don't think that's really right. The model is part of the
>>definitions of P and NP. Either P=NP or it doesn't.
>
> Well, this is just a quibble, isn't it?

I thought I made that clear.

> We can read "P" to mean "problems
> solvable in deterministic polynomial time" and "NP" to mean "problems
> solvable in nondeterministic polynomial time," where the model of
> computation is implicit and can vary.

They had perfectly good meanings already. Playing loose with the
definitions is a frequent cause of stupid arguments.


--
--Bryan
First  |  Prev  |  Next  |  Last
Pages: 1 2 3 4 5 6 7 8 9
Prev: HEAP SORT
Next: Greedy Algorithm