From: Matt Mahoney (matmahoney@yahoo.com)
Date: Wed Oct 21 2009 - 09:57:49 MDT
Pavitra wrote:
> Thus, "there exists at least one NP-complete problem solvable in
> polynomial time" is equivalent to "P = NP", and "there exists at least
> one NP-complete problem not solvable in polynomial time" is equivalent
> to "P != NP".
No. "Traveling Salesman" is an NP-complete problem. But suppose I have n cities equally spaced at 1 mile intervals on a circle. Then I know (and can prove in polynomial time) that the shortest path for these instances is n miles.
Other instances may have more subtle shortcuts, but you don't know which ones. A proof of P != NP would only say that not all instances of a problem do.
-- Matt Mahoney, matmahoney@yahoo.com
----- Original Message ----
From: Pavitra <celestialcognition@gmail.com>
To: sl4@sl4.org
Sent: Wed, October 21, 2009 12:00:58 AM
Subject: Re: [sl4] to-do list for strong, nice AI
Matt Mahoney wrote:
> 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.
I thought the definition of NP-complete was that if any single
NP-complete problem is solvable in polynomial time (i.e, is in P), then
any problem in NP is solvable in polynomial time.
Thus, "there exists at least one NP-complete problem solvable in
polynomial time" is equivalent to "P = NP", and "there exists at least
one NP-complete problem not solvable in polynomial time" is equivalent
to "P != NP".
That is, I believe that "there exists at least one NP-complete problem
solvable in polynomial time, and at least one other NP-complete problem
not solvable in polynomial time" has been mathematically disproven.
Am I completely missing the point?
This archive was generated by hypermail 2.1.5 : Wed Jul 17 2013 - 04:01:05 MDT