From: Luke (wlgriffiths@gmail.com)
Date: Thu Oct 22 2009 - 13:09:58 MDT
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