发信人: wasguru()
整理人: bsese(2000-05-31 10:33:19), 站内信件
|
这已经是1995年的事了，当时费马最后定理刚刚获得证明。
P=NP is the most famous unsolved problem in computer science,
analogous to Fermat's Last Theorem, although the P=NP problem has
only been around for about 30 years, 25 maybe. In the context of
combinatorial algorithms, it says: Are we going to be able to
solve problems that would require going through 2^n cases? Can we
actually do those in n^10, or something like that, if we knew the
best method? if P=NP, the answer would be "yes", with some
polynomial: we could reduce all these exponential problems to
polynomial problems. If not, the answer is "no", we'll never to
able to reduce them.
I have a feeling that someone might resolve the problem in the
worst possible way, which is that following. Somebody will prove
that P is equal to NP because there are only finitely many
obstructions to it not being equal to NP. [laughter] The result
would be that there is some polynomial such that we could solve
all NP problems in polynomial time. However, we won't know what
the polynomial is; we'll just know that it exists. So maybe the
complexity will be n to the trillionth or something like that ---
but it'll be a polynomial. In such a scenario we'll never be able
to figure it out because it would probably take too long to find
out what the polynomial is. But it might exist. Which means that
the whole question P=NP was the wrong question![laughter] It might
go that way. You see, even if you have a method that takes 2^n
steps and you compare it to a method that takes n^100, then at
least you can use the 2^n one for n up to 20 or 30. But the n^100
you can't even do for n=2. So the degree of that polynomial is
very important. There are so many algorithms out there, the task
of showing that no polynomial algorithms exist is going to be very
hard. Still, I really thought that Fermat's Theorem was a similar
kind of thing, where it was more important to have the problem
than to solve it. Therefore, my real feeling about Wiles's Theorem
is that he did a marvelous wonderful piece of work, but I wish
he'd solved something else! [laughter]
A lot of people think that as soon as a problem is shown to be in
this class NP, they shouldn't work on it, because it means that
there's probably no polynomial way to solve the problem. But
before we studied NP, we had unsolvable problems --- problems for
which there didn't exist any algorithms at all. No matter how long
you worked, you could never solve the problem. To tell whether a
given Turing machine ever stops: This problem is unsolvable by any
algorithm, in general, no matter how long you give yourself. In
the days before NP became famous, people would stop working on a
problem as soon as it was proved to be unsolvable in general. But
that was a bad strategy, because almost every problem we ever
solve is a special case of some unsolvable problem.
Take calculus, for example --- the problem of taking a formula, a
function of n, and saying: "Is the limit as n goes to infinity
equal to zero or not?" That's an unsolvable problem. But its
unsolvability doesn't imply that we shouldn't study calculus. I
mean, limits of lots of useful functions do go to zero, and
therefore people were able to develop calculus. But the general
problem is unsolvable. I mean, you could define f of n --- it only
takes a few lines to make a formula that is equal to zero if a
given Turing machine is stopped at time n, and it's equal to 1 if
the Turing machine is still going at time n. And so the limit is
equal to zero if and only if that Turing machine stops. It's
unsolvable.
A similar thing happens with NP. That is, we have lots of special
cases of problems that are NP-hard that we can solve efficiently;
just knowing that something is NP doesn't mean that it's a good
idea to give up on it or to stop trying to get good heuristic
methods for it.
--
※ 来源:．月光软件站 http://www.moon-soft.com．[FROM: 144.92.44.76]
|
|