From: Matt Mahoney (matmahoney@yahoo.com)
Date: Tue Oct 20 2009 - 20:13:04 MDT
Pavitra wrote:
> Just to check: I think you mean "...even if it turns out that P = NP"?
No, I mean P != NP. Suppose it were proven. You would know that some instances of, say, SAT or traveling salesman required exponential time to solve, but you wouldn't know which ones. There are heuristics that can solve lot of NP-complete problems quickly, just not all of them. You don't know that any particular instance is hard because there might be another heuristic that makes it easy.
Cryptography has a similar problem. No algorithm with keys shorter than the message (i.e. not one-time pad) is provably secure. We only trust algorithms after lots of people try to break them and fail to do so. But we continue to be surprised. Everyone thought MD5 was secure. And who would have guessed that RSA could be broken with a quantum computer?
-- Matt Mahoney, matmahoney@yahoo.com
----- Original Message ----
From: Pavitra <celestialcognition@gmail.com>
To: sl4@sl4.org
Sent: Tue, October 20, 2009 9:15:56 PM
Subject: Re: [sl4] to-do list for strong, nice AI
Matt Mahoney wrote:
> In fact there are *no* classes of problems that are known to be hard
> to solve but easy to check. That's true even if it turns out that P
> != NP, because you still don't know *which* NP-complete problems are
> hard, just that some of them are.
Just to check: I think you mean "...even if it turns out that P = NP"?
This archive was generated by hypermail 2.1.5 : Wed Jul 17 2013 - 04:01:05 MDT