**From:** Pavitra (*celestialcognition@gmail.com*)

**Date:** Tue Oct 20 2009 - 22:00:58 MDT

**Next message:**Tim Freeman: "How big is an FAI solution? (was Re: [sl4] to-do list for strong, nice AI)"**Previous message:**Gwern Branwen: "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:**Matt Mahoney: "Re: [sl4] to-do list for strong, nice AI"**Reply:**Matt Mahoney: "Re: [sl4] to-do list for strong, nice AI"**Messages sorted by:**[ date ] [ thread ] [ subject ] [ author ] [ attachment ]

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?

- application/pgp-signature attachment: OpenPGP digital signature

**Next message:**Tim Freeman: "How big is an FAI solution? (was Re: [sl4] to-do list for strong, nice AI)"**Previous message:**Gwern Branwen: "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:**Matt Mahoney: "Re: [sl4] to-do list for strong, nice AI"**Reply:**Matt Mahoney: "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
*