# Re: [sl4] to-do list for strong, nice AI

From: Matt Mahoney (matmahoney@yahoo.com)
Date: Fri Oct 23 2009 - 12:16:15 MDT

> 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.

It depends what you mean by "intelligence". If you mean time to solve the problem, that's not been proven because we don't know that P != NP.
-- Matt Mahoney, matmahoney@yahoo.com

________________________________
From: Luke <wlgriffiths@gmail.com>
To: sl4@sl4.org
Sent: Thu, October 22, 2009 3:09:58 PM
Subject: Re: [sl4] to-do list for strong, nice AI

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

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