Hacker News Reader

Comment by FartyMcFarter | Hacker News Reader

> What's the most efficient algorithm you can write to do this? As it turns out, you can't do well in the worst case — and we'll prove this by a reduction from SAT.

Correction: you can't do well in the worst case, assuming P ≠ NP (where "well" means "in polynomial runtime").

View on HN

Pedantic and wrong. Considering there is no known algorithm that can sat solve in P, nobody in the world can do well in the worst case. And if nobody can do it, then you can't do it either, for any you. QED.

I'm not a native English speaker, but I thought "you can't do well" is equivalent to "it's impossible to do well", which is how I read the original sentence.

As an aside, I find it a bit ironic that you're complaining about pedantry while interpreting the "you" word literally.

It’s not ironic that my response was pedantic, it was the entire point. When you engage in pedantic nerd sniping you just open yourself up for even more pedantic nerd sniping.

“Can’t” can mean impossible, or it can mean nobody can do it. Compare “you can’t go back in time” with “you can’t lift a horse”.

It's awkward to abbreviate "in polynomial time" as "in P". P is a set of (decision) problems. We don't know that 3-SAT is in P. We don't know that it's not.

To say that a solver is not in P is a type error.

Your “proof” it’s more like. No one has ever stepped on Mars. Therefore no one will.

Yet another pedantic fallacy.

Not that no one will, just that no one can

I give you until the end of today to show me someone (anyone!) step on Mars

It was just someone being cheeky about someone being cheeky. Now I'm being cheeky about you being cheeky over someone being cheeky about someone being cheeky

Reply on news.ycombinator.com