Comment by eru
4 years ago
> First, I personally consider NlogN the bar for "efficient" as far as algorithms go. Anything polynomial is inefficient, and anything better than NlogN is like, "super efficient" in my mind.
What is efficient and what ain't depends totally on context.
For example, for some domains even proving that a problem is in NP (instead of something worse), means that they consider the problem tractable, because we have good solvers for many NP hard problems in practice.
For other domains, you want O(1) or O(log n) or O(log* n) etc.
In general, P vs NP is such a big deal, because polynomial runtime is generally seen as tractable, and anything worse as intractable.
(Btw, O(n log n) _is_ a polynomial runtime, and so is O(N) or even O(1). Though I can see that as a shorthand of notation you are excluding them.)
> (Btw, O(n log n) _is_ a polynomial runtime, and so is O(N) or even O(1). Though I can see that as a shorthand of notation you are excluding them.)
I mean yes, technically n^1 is a polynomial, but normally this is just called linear. You hit the nail on the head with the last sentence. Here I'm using polynomial to basically mean "n^k, k>1". From a NP vs P point of view, P is considered tractable. But from a "actually writing libraries" point of view, I think software developers consider O(n^2) "kinda bleh" if it can be at all avoided. Also developers tend to give much more weight to the actual coefficients / parallelism potential / practical runtime. Neural networks have superlinear bounds everywhere, but GPU goes brrr.
Brass tacks, sorting some tuples and diffing the rank then reducing strikes me as likely to be:
- pretty fast even in the naive implementation
- sorting is a well trodden field
- easy to write things like shaders for
- amenable to speculative execution
- amenable to divide and conquer
So that is what I mean by efficient.
The “P” in NP means a solution to a decision problem is verifiable in polynomial time.
The “N” in NP means the solution can be produced by a non-deterministic Turing machine (i.e. a computer that can search the problem space in many dimensions in each step).
NP does not mean “non-polynomial” time to produce a solution, otherwise P != NP by definition. Instead P is a subset of NP.
The open question is if all decision problems with solutions verifiable in polynomial time can also be produced in polynomial time.
Yes.
I know that the N stands for non-deterministic. Read my comment carefully, it agrees with everything you write here. (Or at least, does not disagree. It's silent on most of the intricacies.)
For many people moving a problem from NP to P means the same as having a tractable solution. See eg Scott Aaronson's writing on the topic.
> Read my comment carefully
Please take a spoon of your own medicine and read my comment even more carefully. I never suggested my comments were a contradiction to yours.
I added some information for bystanders that may have read your comment and come to (or reinforced) a wrong conclusion.
2 replies →