3 ms·

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

by cratermoon 3y ago

EA 3y ago
And yet it never uses the word "polynomial".
- svat 3y ago
  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 https://en.wikipedia.org/wiki/Cobham%27s_thesis
  - krackers 3y ago
    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.
chippiewill 3y ago
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.
- cratermoon 3y ago
  > still actually wrong Can you be specific about where it's wrong? For the layperson?
- kzrdude 3y ago
  Non-deterministic should be explained more often because it's meaning in computer science is nonintuitive.
FranklinMaillot 3y ago
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 https://youtu.be/rK3xcRYLWeg

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

EA 3y ago

And yet it never uses the word "polynomial".

svat 3y ago
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 https://en.wikipedia.org/wiki/Cobham%27s_thesis
- krackers 3y ago
  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.

chippiewill 3y ago

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.

cratermoon 3y ago
> still actually wrong Can you be specific about where it's wrong? For the layperson?
kzrdude 3y ago
Non-deterministic should be explained more often because it's meaning in computer science is nonintuitive.

FranklinMaillot 3y ago

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 https://youtu.be/rK3xcRYLWeg