Hacker News Reader

Comment by cratermoon | Hacker News Reader

This article has the best lay-friendly explanation of what P vs NP means that I've seen.

I think this video does a much better job. It places the problem in the historical context of computer science and explains why it's an important question. It's also more in depth while still being very short and approachable.

I highly recommend the channel if you're interested in information theory. It's just starting to publish new videos after a very long hiatus.

https://youtu.be/rK3xcRYLWeg

It's good purely from being lay-friendly, but I really wish they didn't labour their specific description so much because while it's an intuitive explanation it's also still actually wrong.

Also if you're going to write an article that long about P and NP then as the other commenter mentioned, it would be nice to mention the words polynomial and non-deterministic.

Non-deterministic should be explained more often because it's meaning in computer science is nonintuitive.

> still actually wrong

Can you be specific about where it's wrong? For the layperson?

And yet it never uses the word "polynomial".

It uses "efficient" everywhere, only alluding to polynomial-time here:

> Theoretical computer scientists use a technical definition for “efficient” that can be debated, but it serves as a useful proxy for the colloquial concept.

The idea that “polynomial-time” and “efficient” are reasonable proxies for each other is the Cobham–Edmonds thesis: https://en.wikipedia.org/wiki/Cobham%27s_thesis

I don't see how this statement is useful, because if an alg is "tractable" iff it is poly-time then n^10 algorithms would be considered "tractable". I think the real reason we care about P in a CS-theoretic sense is because it's a closed group under various operations, which allows us to talk about things in an implementation-oblivious fashion.

In practice in the real world we care only about low-degree P though (usually n < 3 at most), are really interested in linear & nlogn, and care about constant factors.

There's also Quasi-Polynomial time algorithms which are interesting because they straddle the line between P and EXPTIME.

Reply on news.ycombinator.com