Fortnow's paper regarding the status of the P vs. NP problem
cplxphil
In his recent paper, "The status of the P vs. NP problem," Lance
Fortnow writes,
"[If P = NP is true, l]earning becomes easy by using the principle of
Occam's razor—we simply find the smallest program consistent with the
data. Near perfect vision recognition, language comprehension and
translation and all other learning tasks become trivial. We will also
have much better predictions of weather and earthquakes and other
natural phenomenon."
The paper can be found here:
http://cacm.acm.org/magazines/2009/9/38904-the-status-of-the-p-versus-np-problem/fulltext
What does he mean? I wasn't aware that the problem of finding general
algorithms to solve problems like vision recognition or language
comprehension was in NP. Could anyone shed some light on what he
means? Also...how would weather and earthquakes be predicted via a
solution to NP-complete problems.
Thanks,
Phil
Tim Little
> What does he mean? I wasn't aware that the problem of finding general
> algorithms to solve problems like vision recognition or language
> comprehension was in NP.
It isn't. What's more, finding "the smallest program consistent with
the data" is not in NP either. It is uncomputable, since solving that
problem implies determining the Kolmogorov complexity of arbitrary
sequences.
- Tim
tc...@lsa.umich.edu
Tim Little <t...@little-possums.net> wrote:
>It isn't. What's more, finding "the smallest program consistent with
>the data" is not in NP either. It is uncomputable, since solving that
>problem implies determining the Kolmogorov complexity of arbitrary
>sequences.
Right. Fortnow does give a caveat in his article, "This article does not
try to be totally accurate or complete either technically or historically."
I don't think Fortnow meant to say anything more than this: In many of
those problems (weather forecasting, voice recognition, etc.), we can
often quickly recognize a good solution when we see one, and the problem
is to *find* the good solution. If there were an efficient solution to
an NP-complete problem then finding a solution would be (almost) as easy
as recognizing a solution.
--
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
cplxphil
> In article <slrnhf6k85.n6v....@soprano.little-possums.net>,
Hmmm...are you saying that he is reasoning by way of analogy? What
puzzles me the most is this part: "using the principle of Occam's
razor—we simply find the smallest program consistent with the data."
I had a similar idea along these lines myself once, which is why I was
so intrigued by this line. Maybe there isn't a single algorithm that
would find the solutions to these problems, but perhaps a human-
assisted program could.
Suppose we want to build a chess-playing robot. All we'd need is an
algorithm to determine if any particular position is "winning" or
not. (As a caveat of my own, I've read that position evaluation in
"generalized chess" is EXPTIME-complete.) Anyway, if we make the
fairly-reasonable assumptions that no game will go on for more than
500 moves and that no algorithm that runs in slower than 50,000,000
steps for a given position is acceptable (since the input size is
constant-bounded I give a constant upper bound for the input), then we
can construct an NP algorithm for checking all the moves of a game (to
checkmate or a draw) to see if they are optimally played. If P = NP,
we can use that algorithm to determine if a line of play from a
position to the end of the game is optimal in polynomial time. Then,
using *that* algorithm, we can construct an algorithm that will check
positions for being "winning" by seeing if there is an optimal line of
play for both sides that leads to victory for the player. Obviously,
then the chess playing robot should only make moves that yield winning
positions.
The idea would be that to search for these algorithms, we just
restrict the size of the algorithm that we'll look for. There are a
lot of arbitrary decisions that would be made regarding running time
and the length of the game, but it seems that some of these algorithm-
finding problems might become feasible, even if the solutions to them
aren't clean.
I'm wondering if this is essentially what Fortnow was getting at...I
don't always trust my own intuition on these things. Anyway, I sent
him an e-mail and I'll see if he replies.
Thank you both Tims for the replies; anyone have any other thoughts?
-Phil
Tim Little
> fairly-reasonable assumptions that no game will go on for more than
> If P = NP, we can use that algorithm to determine if a line of play
> from a position to the end of the game is optimal in polynomial
> time.
Given the constraint you can do it in constant time, regardless of
whether P=NP or not. There is an upper bound on how many games there
are, so in principle you can just make a table of them and return the
correct answer.
> There are a lot of arbitrary decisions that would be made regarding
> running time and the length of the game, but it seems that some of
> these algorithm- finding problems might become feasible, even if the
> solutions to them aren't clean.
The biggest obstacle is that verifying that an algorithm runs in
polynomial time is not in general an operation that can be conducted
in polynomial time. It is not even computable whether it returns a
result at all.
However, there are certainly interesting implications: verifying the
correctness of a formal proof is a polynomial-time operation. If
P=NP, finding a proof or disproof for some proposition is then a
polynomial-time operation in the length of the shortest proof or
disproof.
Of course there's nothing to say that it isn't O(n^100), so it may
still be impractical even if P=NP.
- Tim
tc...@lsa.umich.edu
Tim Little <t...@little-possums.net> wrote:
>The biggest obstacle is that verifying that an algorithm runs in
>polynomial time is not in general an operation that can be conducted
>in polynomial time. It is not even computable whether it returns a
>result at all.
Technically, you are correct, but this is not actually a serious obstacle.
One can restrict to Turing machines that are "polynomially clocked"; that
is, the operating system forces the algorithm to stop after n^3 steps (or
whatever polynomial you want) and outputs "no" if the algorithm hasn't
made up its mind yet by then. Any polynomial-time algorithm that is
computable by a Turing machine is also computable by a polynomially clocked
Turing machine, and for polynomially clocked machines we don't have any
undecidability problems.
Basically, Phil, your intuition is sound, and if Fortnow writes back, there
is a good chance that he will just say what you've already said. The idea
goes all the way back to Goedel's "lost" letter to von Neumann, in which he
pointed out that one can circumvent the undecidability of theoremhood by
putting a bound on the length of the proof we're willing to search for.
Then the problem becomes an NP-complete problem.
cplxphil
To Tim Little:
Ah, good point about the constant time. Perhaps I should have left
out the bit about 500 moves max. However, that said, I think that
"very large constant-bounded time" is not preferable to reasonable
polynomial time; i.e., if I have an algorithm that runs in time O
(n^3), I'd (usually) rather have that than an algorithm that runs in
time bounded by the constant one googol, particularly if the latter
algorithm usually takes close to the worst-case. Your point is well-
taken though...I just think that the table you refer to would be hard
to parse.
I agree that calculating whether or not an algorithm runs in
polynomial time is undecidable. In addition to the fact that this
would make it easy to resolve P vs. NP (just check Levin's algorithm
to see if it's polynomial time), the poster Jym described a very
clever variant on the proof of Rice's theorem some time ago on
comp.theory proving that polynomial-time testing is undecidable for
algorithms. Actually, though, I think that this follows directly from
Rice's theorem, also; but the proof was still nice, in my opinion.
To Tim Chow:
Thanks for the insights. I particularly like the point about
rendering an undecidable problem NP-complete by putting bounds on it
(provided of course that there's a good checking algorithm). I think
that's how I'll think about the chess problem and other AI-type
problems...if you need an AI, you enforce arbitrary but reasonable
bounds on the algorithm and/or on the problem it's supposed to solve,
and then the problem becomes NP-complete, provided the existence of a
"good" checking algorithm. If you need a checking algorithm, you can
(hopefully) use the same process to generate that.
I will have to do some Googling and find Godel's lost letter to von
Neumann...I've heard of it before, but I should try to find it and
read the original text.
tc...@lsa.umich.edu
cplxphil <cplx...@gmail.com> wrote:
>I will have to do some Googling and find Godel's lost letter to von
>Neumann...I've heard of it before, but I should try to find it and
>read the original text.
This means you haven't found Lipton's blog yet. I'm sure you'll enjoy
following Lipton's blog.
cplxphil
> In article <5f541af1-3f44-4648-981b-8aa2aa29f...@m26g2000yqb.googlegroups.com>,
>
> cplxphil <cplxp...@gmail.com> wrote:
> >I will have to do some Googling and find Godel's lost letter to von
> >Neumann...I've heard of it before, but I should try to find it and
> >read the original text.
>
> This means you haven't found Lipton's blog yet. I'm sure you'll enjoy
> following Lipton's blog.
> --
> 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
I looked up Lipton's blog, and from what I've read so far I like it a
lot. On the subject of his most recent post, I think I may have a
"mathematical disease," I was actually thinking about that the other
day...I really can't stop thinking about the P = NP problem, although
I know that I can't really contribute anything to the field, at least
not yet (plans for higher education and/or a relevant job are in the
works but not yet realized). I've learned to embrace the addiction, I
guess.
On a less depressing note, Fortnow replied to my e-mail, and his
response is actually more interesting than what I had imagined. Since
I didn't ask him for permission to reproduce his e-mail verbatim, I'll
explain what he said in my own words.
In his e-mail, Fortnow used the example of language translation.
Suppose I have a huge body of Portuguese text and a translated version
of that text in German (I chose two languages I know nothing about).
For a program X, consider the value C (as in complexity) of the
program that is calculated based on some measure of the running time
of X plus the size of X. So, C = running time + size. Find the value
of X that minimizes C for a sufficiently large data set, and you
should have a good translator.
If you choose too small of a body of text, you will find that the
program doesn't work; but assuming the existence of a good translator
program, if you choose a sufficiently large body of text, the
algorithm should find a "good" translator algorithm.
Fortnow said that there are also better examples using Bayesian
learning, and that he would write up more details someday.
I think the chess problem might be a little different from language
translation as it's a mathematically well-defined game...but I was
very happy with the explanation.
-Phil
Tim Little
> Technically, you are correct, but this is not actually a serious obstacle.
> One can restrict to Turing machines that are "polynomially clocked"; that
> is, the operating system forces the algorithm to stop after n^3 steps (or
> whatever polynomial you want) and outputs "no" if the algorithm hasn't
> made up its mind yet by then.
I may have lost track of the original idea here (and cannot search the
preceding posts at the moment), but I don't think this solves it.
The idea seemed to be that we are searching the space of
polynomial-time algorithms, looking for one that solves a given NP
problem. We really need two oracles: one that tells us that the
algorithm is correct for all inputs, and another that tells us that
the algorithm runs in polynomial time for all inputs.
As you say, we can force all algorithms to run in polynomial time to
eliminate one oracle. For any given polynomial we can terminate all
test algorithms after that many steps and consider their answer to be
"no solution". We know that there exists a polynomial for which some
algorithm will still always produce the correct solutions but
regardless of whether P=NP, we still don't know which polynomial or
which algorithm.
- Tim
tc...@lsa.umich.edu
Tim Little <t...@little-possums.net> wrote:
>The idea seemed to be that we are searching the space of
>polynomial-time algorithms, looking for one that solves a given NP
>problem. We really need two oracles: one that tells us that the
>algorithm is correct for all inputs, and another that tells us that
>the algorithm runs in polynomial time for all inputs.
>
>As you say, we can force all algorithms to run in polynomial time to
>eliminate one oracle. For any given polynomial we can terminate all
>test algorithms after that many steps and consider their answer to be
>"no solution". We know that there exists a polynomial for which some
>algorithm will still always produce the correct solutions but
>regardless of whether P=NP, we still don't know which polynomial or
>which algorithm.
Going back and reading Phil's proposal more carefully, I think that you
are right.
If we "bound" generalized chess by asking the question, "Can checkmate
be forced from this position in logarithmically many moves?" then the
problem becomes NP. Similarly, many other problems, even undecidable
ones, can be put into NP if a suitable bound is introduced.
However, Phil was talking about the problem of *finding a polytime
algorithm* for something. I don't see how to "bound" such a problem
to put it in NP. If someone shows me such an algorithm, I can verify
that it runs in polynomial time if we agree on a convention that forces
the algorithm to run in polynomial time. But how do I verify that
the algorithm correctly solves the problem it is supposed to solve?
This can't be done unless we do something like fix the size of the input
to the algorithm to be some absolute constant like 100 bits.