Hacker News Reader

Comment by chx | Hacker News Reader

One problem here ... it needs to come with a huge caveat: this is much more a theoretical discussion than necessarily a practical one.

This is to say, it's possible for a problem the best P algorithm we can find takes n^(10^82) time while the NP algorithm we can find is say (1.00000000.....(10^82 zeroes)... 1)^n. For any practical number the NP algorithm will be faster. (I used 10^82 because it's the approximate number of atoms in the observable universe.)

View on HN

Yes, the class P is huge. Calling problems in P "easy" is severely misguided. We have only barely scratched the surface of this class (linear and quadratic problems), but there is an infinitely deep ocean of problems below the surface that we cannot even imagine. It is illuminating to recall Knuth's view that probably P=NP, but it won't have any practical effect.

Yes, I agree. Complexity theory is probably one of the least practical fields for software _engineers_, it can even work to a detriment, because you can discouraged to find solutions to problems.

On the other hand, I have had great benefit from studying PL and semantics for software engineering. It taught me to write more readable and reliable code.

(From a person who studied both as a part of his master)

Quite the opposite actually! Imagine you encounter an optimization problem in your daily work and want to solve it algorithmically. You study the problem a little and find that it contains the knapsack problem as a sub case. Now you know the problem is NP-hard and don't need to waste time trying to solve it. Instead, you can think of ways to modify the problem or decide if you're fine with approximating the solution to some meaningful accuracy.

You don't need to involve a P vs NP discussion at all if you want to have a practical discussion to begin with. Big-Oh is sufficient?

Profiling the code with different size inputs is sufficient

I don’t know, I think knowing what algorithmic complexity is is really important, the problem is that all too many people just memorized that bubble sort is O(n^2) without understanding.

Also, the reason why profiling is imo not good enough is that you really shouldn’t even try to write an implementation with a known-to-be “slow” algorithm at the designed input size. For that, understanding O-notation is essential.

Reply on news.ycombinator.com