**From:** Johnicholas Hines (*johnicholas.hines@gmail.com*)

**Date:** Wed Oct 21 2009 - 12:11:48 MDT

**Next message:**Tim Freeman: "Re: How big is an FAI solution? (was Re: [sl4] to-do list for strong, nice AI)"**Previous message:**Matt Mahoney: "Re: How big is an FAI solution? (was Re: [sl4] to-do list for strong, nice AI)"**In reply to:**Matt Mahoney: "Re: [sl4] to-do list for strong, nice AI"**Next in thread:**Luke: "Re: [sl4] to-do list for strong, nice AI"**Messages sorted by:**[ date ] [ thread ] [ subject ] [ author ] [ attachment ]

ALL instances of a problem DO have shortcuts. Specifically, given an

instance, consider the solver that checks for that instance, and

outputs a pre-computed answer for that instance. That's why we talk

about the hardness of problem families rather than problems.

On Wed, Oct 21, 2009 at 11:57 AM, Matt Mahoney <matmahoney@yahoo.com> wrote:

*> 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?
*

*>
*

**Next message:**Tim Freeman: "Re: How big is an FAI solution? (was Re: [sl4] to-do list for strong, nice AI)"**Previous message:**Matt Mahoney: "Re: How big is an FAI solution? (was Re: [sl4] to-do list for strong, nice AI)"**In reply to:**Matt Mahoney: "Re: [sl4] to-do list for strong, nice AI"**Next in thread:**Luke: "Re: [sl4] to-do list for strong, nice AI"**Messages sorted by:**[ date ] [ thread ] [ subject ] [ author ] [ attachment ]

*
This archive was generated by hypermail 2.1.5
: Wed Jul 17 2013 - 04:01:05 MDT
*