search

imposters-handbook / feedback

General typos, issues, clarifications etc for The Imposter's Handbook
78 stars 2 forks source link

NP Interview Question: phrasing muddles the point of complexity #106

Closed joneda closed 8 years ago

joneda commented 8 years ago

I don't think that the interview question is overly complicated. It seems like something that would be O(sqrt(N)). I created some javascript that I think correctly handles the problem, and runs in milliseconds. https://jsfiddle.net/kthro2ew/2/

Perhaps if the question were along the lines of finding all of the prime numbers under 12,883,399,391 instead of finding its prime factors.

robconery commented 8 years ago

Which interview question are you talking about?

robconery commented 8 years ago

Never mind - found it :). A few things to keep my sanity if you don't mind :) - if you want to log an issue, please do. Reading what you wrote here it seems like you just decided to write a JavaScript routine just to see if it could be done.... which it can... but I muddied the whole thing a bit.

So, just to confirm: is your issue that the problem, as stated, doesn't focus clearly enough on prime number factorization being non-polynomial? Or are you saying that you don't think it's in NP?

joneda commented 8 years ago

I don't have a great grasp on NP (one of the reasons I purchased your book :) ). I think what bothered me about the interview question is that it poses a solvable problem and then implies that "I wouldn't try" is the correct answer.

After your reply I went back and read a little about prime factorization. It seems clear that prime factorization is a good example for an NP problem, but current hardware makes the problem for small numbers (like the number used in your example) trivial.

So, in answer to your question, yes. I don't think that the problem, as stated, focuses clearly enough on prime number factorization being non-polynomial. And, in my ignorance I didn't think that it was in NP -- pretty embarrassed about that right now. :$

robconery commented 8 years ago

That's the idea of knowing if something is in NP :). Like the traveling salesman - you wouldn't believe how many times someone has dreamed up an idea that resolves to the same problem.

The thing about it is scaling, not so much the actual effort to produce the smaller results. Either way: I'll clarify this chapter a bit more so it's apparent :).