ASCII Code

[Provost Harrison]

I'm nearly there, only a few decades to go!

[Lul Thyme]

Originally posted by Kuciwalker
In addition, a naive approach to the Google one wouldn't work, because it's O(sqrt(n)).

The fact that it's O(sqrt(n)) in itself doesn't mean anything about whether a particular problem is solvable by naive approach. It depends on the constants involved and the size of the problem, among other things.

Asymptotics are all very important, but they don't tell the whole story, and sometimes even tell the wrong story in practical problems.

EDIT1:
you still havn't explained why it being harder to find the "answer" in this case make it lame.
Is google the new threshold for "lameness" for such type of ads in the future?

EDIT2:I really don't see how the naive approach wouldn't work.
From the prime number theorem, the density of primes for 10 digit numbers is about 5%. If the digits of e were random (which they are believed to be for many different definitions), you would expect to find the first prime after 20 tries. (I think in this particular problem, it takes about 100 numbers).
The most naive approach:
-write a script to extract the sequence of 10 digit number from e
-test whether each is prime using the Miller Rabin on Mathematica, say (which is default for such test)

finds the answer in minutes...


Again, it's nice to be able to quote some nice asymptotic results, but it's ever nicer to know when to apply them.

[padillah]

Originally posted by Lul Thyme


The fact that it's O(sqrt(n)) in itself doesn't mean anything about whether a particular problem is solvable by naive approach. It depends on the constants involved and the size of the problem, among other things.

Asymptotics are all very important, but they don't tell the whole story, and sometimes even tell the wrong story in practical problems.

EDIT1:
you still havn't explained why it being harder to find the "answer" in this case make it lame.
Is google the new threshold for "lameness" for such type of ads in the future?

EDIT2:I really don't see how the naive approach wouldn't work.
From the prime number theorem, the density of primes for 10 digit numbers is about 5%. If the digits of e were random (which they are believed to be for many different definitions), you would expect to find the first prime after 20 tries.
You can plug them in Mathematica by hand, running a Miller Rabin for primality, and find the answer in minutes.
Seems pretty straightforward and "naive" to me.

I understood the numbers, 10 and 20, and that's about it.

I thought there was no way to test for primes? Finding prime numbers is NP-complete, right? You just have to look for them. Or am I missing the biggest mathematical breakthrough in the last 200 years?

Seriously though, I thought you couldn't "test" for primality without just dividing by each number along the way.

Tom P.

[Kuciwalker]

Originally posted by Lul Thyme
The fact that it's O(sqrt(n)) in itself doesn't mean anything about whether a particular problem is solvable by naive approach. It depends on the constants involved and the size of the problem, among other things.

Asymptotics are all very important, but they don't tell the whole story, and sometimes even tell the wrong story in practical problems.

In this case it makes the problem impossible. Given the computing resources available to the average person it would take them a very long time to find the answer using the naive approach, whereas using the method I mentioned would get it in seconds.

(We actually had a variant on this problem in class, except with pi instead of e, and there were time constraints...)

-test whether each is prime using the Miller Rabin on Mathematica, say (which is default for such test)

By naive approach I meant for each number N, loop from 1 to sqrt(N) and check if its divisible. The practical approach is Miller-Rabin.

Again, it's nice to be able to quote some nice asymptotic results, but it's ever nicer to know when to apply them.

And this was such a case, thank you.

[Lul Thyme]

Originally posted by padillah


I understood the numbers, 10 and 20, and that's about it.

I thought there was no way to test for primes? Finding prime numbers is NP-complete, right? You just have to look for them. Or am I missing the biggest mathematical breakthrough in the last 200 years?

Seriously though, I thought you couldn't "test" for primality without just dividing by each number along the way.

Tom P.

There are algorithm that test for primality of course.
You just described one:
-divide by all smaller primes.
It's just that it's very inefficient.
There are much better algorithms, though, contrary to what you believe.
Some are probabilistic, like Miller-Rabin.

Until recently, it was thought that primality testing was not in P, but in 2004, Manindra Agrawal, Neeraj Kayal, Nitin Saxena found a polynomial primality testing algorithm. Note that it is NOT A factorization algorithm, which is important. So NO , primality is not NP complete, in fact it's in P!. As far as I know, it was never believed to be NP Complete. (Note that not being in P and being NP complete is not nec. the same thing).

It is known if prime factorization is in P or not, and whether it is NP complete. It is generally believed to be neither, whatever weight that holds.

[Kuciwalker]

Originally posted by Lul Thyme
you still havn't explained why it being harder to find the "answer" in this case make it lame.
Is google the new threshold for "lameness" for such type of ads in the future?

Google does a cute, geeky ad that requires just a little bit of thought to complete (for the intended audience).

Later, EA does another geeky ad, except it's completely trivial - type that in and add printf and you have the answer. Meh. It's a copycat and a poor one. Thus, lame.

[Kuciwalker]

Originally posted by Lul Thyme
It is known if prime factorization is in P or not, and whether it is NP complete. It is generally believed to be neither, whatever weight that holds.

I thought prime factorization was NP-complete... hm. It's obviously in NP.

[Lul Thyme]

Originally posted by Kuciwalker


In this case it makes the problem impossible. Given the computing resources available to the average person it would take them a very long time to find the answer using the naive approach, whereas using the method I mentioned would get it in seconds.

(We actually had a variant on this problem in class, except with pi instead of e, and there were time constraints...)

-test whether each is prime using the Miller Rabin on Mathematica, say (which is default for such test)

By naive approach I meant for each number N, loop from 1 to sqrt(N) and check if its divisible. The practical approach is Miller-Rabin.


And this was such a case, thank you.

Well sure you can always find dumber ways to do almost anything.
Even YOUR naive method is really smart compared to some other methods I could describe.
I don't see how checking each number in mathematica one by one using the Prime[n] function is anything but naive.

[Lul Thyme]

Originally posted by Kuciwalker


I thought prime factorization was NP-complete... hm. It's obviously in NP.

Experts think it would be very surprising if it is NP complete.

[Lul Thyme]

There's a whole hierarchy of levels of methods.

1.Make a list of 10-digit primes, and look for match.
2.Your "naive" method (try each number, and use trial division)
3.My method (try each number in mathematica)
4.Some meta method , like asher described, you could probably write a script that tries all 10 digit numbers from e in order on internet or something like that.

(and more of course)

You arbitrarly decide that naive methods are 2 and lower, while I think that 3 and lower are all naive.
For example, I hadn't really thought about things like number 4, but some people probably thought of those first and it could be argued that those are also "naive" in certain sense.
Some other people could argue that something like 2 is obviously much better than number 1, and number 1 is the true "naive" method.


Point is, naive doesn't have a fixed meaning, and what I think of the naive solution to such a problem turns out to work very well.

[padillah]

I thought everything was in NP. The difference comes in being in P (can "prove" it quicker than "solve" it) or being NP Complete (absolutly cannot prove it without solving it completly).

So being "in NP" is not really noteworthy.

Again, I'm not a mathmetician... but I'm getting a lot out of this.

Tom P.

[Lul Thyme]

Originally posted by Kuciwalker


Google does a cute, geeky ad that requires just a little bit of thought to complete (for the intended audience).

Later, EA does another geeky ad, except it's completely trivial - type that in and add printf and you have the answer. Meh. It's a copycat and a poor one. Thus, lame.

To anyone that has access to a computer algebra system, the google one is also trivial.
Print out the numbers and check for primalit
If the 3 more lines of codes it requires is enough to take it from lame to cute in your mind, that's fine I guess.

[Kuciwalker]

Originally posted by Lul Thyme
Well sure you can always find dumber ways to do almost anything.
Even YOUR naive method is really smart compared to some other methods I could describe.
I don't see how checking each number in mathematica one by one using the Prime[n] function is anything but naive.

I mention it because one of my groupmates attempted exactly the implementation I described... not every language has a primality test like that built in, and not everyone knows that such a primality test exists (I only knew because I'd seen it in the Java API).

[Kuciwalker]

Originally posted by padillah
I thought everything was in NP. The difference comes in being in P (can "prove" it quicker than "solve" it) or being NP Complete (absolutly cannot prove it without solving it completly).

So being "in NP" is not really noteworthy.

Again, I'm not a mathmetician... but I'm getting a lot out of this.

Tom P.

P = there is a polynomial-time algorithm to find a solution
NP = there is a polynomial-time algorithm to CHECK a solution
NP-complete = any problem in NP can be reduced to such a problem, so if you can solve this in polynomial time you can solve any problem in NP in polynomial time

P is obviously a subset of NP. It's not known whether P = NP or P is a proper subset of NP.

[Lul Thyme]

Originally posted by padillah
I thought everything was in NP. The difference comes in being in P (can "prove" it quicker than "solve" it) or being NP Complete (absolutly cannot prove it without solving it completly).

So being "in NP" is not really noteworthy.

Again, I'm not a mathmetician... but I'm getting a lot out of this.

Tom P.

What do you mean by everything?
Yes, P is inside NP and NP complete is inside NP, but there are also problems that are completly outside this.

EDIT: The halting problem, for example.



In short.
NP means you can solve it non deterministic machine in poly time (or you can check it on a deterministic machine in poly time)

P means you can solve it on a deterministic machine in poly time.

NP complete are the hardest problems in NP. If you solve a NP complete problem in poly time, you can solve all problems in NP in poly time.

So solving a NP complete in poly time is the same as saying P=NP