**From:** Luke (*wlgriffiths@gmail.com*)

**Date:** Thu Oct 22 2009 - 13:09:58 MDT

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

Re: RSA

IF we assume intelligence can be represented by an algorithm (or "set" of

algorithms which are really "modules" of a single all-encompassing

algorithm),

and IF the computer can crack RSA in a couple of days,

THEN the computer is more intelligent than us. Because it has the algorithm

for doing so, and we don't.

And if the computer reports that it's going to take 10^100 years to get the

answer, I'd mark that as "did not give correct answer: FAIL".

Now of course there is the case where you've got the computer can crack it

in 10^5 years, and our best algorithms are expected to take 10^100. In that

case, the computer is more intelligent than us, but we won't know that for

10^5 years. According to my "time limit" method, you've got a false

negative.

But at least it would not produce false positives. And theoretically, after

10^5 years it might take us 1 second to check the answer. So what I said

still holds: "the test-giver does not need to be more intelligent than the

test-taker".

Bringing in NP versus P assumes that by definition NP problems take more

intelligence to solve than P problems. If this conjecture's been proven let

me know.

Finally, @Matt Mahoney: Thank you so much for the Yudkowski definition.

(crap, meant to send this email yesterday but it's sitting here as a draft)

- Luke

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:**Mu In Taiwan: "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:**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
*