Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

NP-hard does not mean hard (2017)

jeremykun.com

Post reply on HN
Print view View original

41–50 of 101 posts

Re: NP-hard does not mean hard (2017)

#41

Post by tgv »

dandanua wrote: post #32
vsnf wrote: post #5

Despite having done my undergrad in CS, I never understood what NP-hard really meant. I mean yeah, polynomial time, boolean logic, general-case not specific-case, transformable into other NP problems, I get it, but like, I don't get it? Anyway, after reading this article I feel like I've gotten one small step closer to filling in this gap in my CS knowledge.

It's probably due to unfortunate naming of things. First, NP doesn't mean "non polynomial", though people can imply that since there are no known polynomial solvers for NP-complete problems. It's a shorthand for "nondeterministic polynomial", but that naming is not intuitive either. It's a class of problems that has polynomial verifiers of solutions. Second, NP-hard means the problem is either NP-complete or not in N…

> Second, NP-hard means the problem is either NP-complete or not in NP at all. Which is another confusing naming, because problems not in NP are NP-hard.

But remember that P is in NP, so NP-hard implies not in P (assuming P ≠ NP).

Re: NP-hard does not mean hard (2017)

#42

Post by aatd86 »

beefield wrote: post #37
vsnf wrote: post #5

Despite having done my undergrad in CS, I never understood what NP-hard really meant. I mean yeah, polynomial time, boolean logic, general-case not specific-case, transformable into other NP problems, I get it, but like, I don't get it? Anyway, after reading this article I feel like I've gotten one small step closer to filling in this gap in my CS knowledge.

> Despite having done my undergrad in CS, I never understood what NP-hard really meant Not having done CS undergrad, I have never really understood even P/NP. The naive explanation of problems that are easy to solve and check vs problems that are difficult to solve but easy to check seems to leave something essential out. I mean, with the naive explanation you are I think you are left with either of two options: 1. A…

Wait, how is it impossible to prove a negative?

Re: NP-hard does not mean hard (2017)

#43

Post by zer8k »

jsolson wrote: post #40
zer8k wrote: post #27

Earlier quoted context omitted.

To add to this NP can also refer to the more formal idea of a non-deterministic turing machine being able to compute the problem in polynomial time. We learned NP as "Non-deterministic Polynomial (time)". I think the more practical definition is "not polynomial"...lol.

Following more or less directly from this: - If you walk backwards from where the non-deterministic Turing machine halted, the list of taken state machine transitions is polynomial in length (naturally, as the machine stopped in polynomial time). - Walking that polynomial length list of actually-taken edges forward through the Turing machine constitutes a polynomial time verification of the solution. This is the esse…

> - If you walk backwards from where the non-deterministic Turing machine halted, the list of taken state machine transitions is polynomial in length (naturally, as the machine stopped in polynomial time).

> - Walking that polynomial length list of actually-taken edges forward through the Turing machine constitutes a polynomial time verification of the solution.

These are really great explanations that would've saved me so much trouble in graduate school. Connecting the automata itself to the term "nondeterministic turing machine" is something that is sorely missed is most CS programs I think. It's usually handwaved in automata theory in order to give you enough to head to compilers. Then you run into it again in graduate school algorithms where it is once again handwaved (because not even the professor fully understands it).

Re: NP-hard does not mean hard (2017)

#45

Post by nine_k »

fooker wrote: post #29
Cerium wrote: post #26

Earlier quoted context omitted.

This is the first I have heard of it as well (and I have properly studied NP complete in graph theory, so I don't know why this missed my attention). It seems that P-complete are difficult to parallelize by definition as they are the set of tractable problems (as opposed to NP) which don't parallelize well. "The class P, typically taken to consist of all the "tractable" problems for a sequential computer, contains th…

It's not by definition, there's a bit of math behind it! :) The intuition is that the hardest problems in P have linear dependency chains. If you could have a good parallel algorithm for a P complete problem, you could take a problem with a dependency chain and solve parts of it in parallel without waiting for the results those parts are depending on.

There is an easy daily example: the PBKDF function, the whole point of which is to be expensive to compute, and impossible to efficiently parallelize.

Re: NP-hard does not mean hard (2017)

#46

Post by beefield »

aatd86 wrote: post #42
beefield wrote: post #37

Earlier quoted context omitted.

> Despite having done my undergrad in CS, I never understood what NP-hard really meant Not having done CS undergrad, I have never really understood even P/NP. The naive explanation of problems that are easy to solve and check vs problems that are difficult to solve but easy to check seems to leave something essential out. I mean, with the naive explanation you are I think you are left with either of two options: 1. A…

Wait, how is it impossible to prove a negative?

Well, I guess you can prove that there are no odd numbers in set (2,4,6), so some negatives you can prove, but in general case, I do not know how to prove that something does not exist and will not exist ever.

Re: NP-hard does not mean hard (2017)

#47

Post by nine_k »

dandanua wrote: post #32
vsnf wrote: post #5

Despite having done my undergrad in CS, I never understood what NP-hard really meant. I mean yeah, polynomial time, boolean logic, general-case not specific-case, transformable into other NP problems, I get it, but like, I don't get it? Anyway, after reading this article I feel like I've gotten one small step closer to filling in this gap in my CS knowledge.

It's probably due to unfortunate naming of things. First, NP doesn't mean "non polynomial", though people can imply that since there are no known polynomial solvers for NP-complete problems. It's a shorthand for "nondeterministic polynomial", but that naming is not intuitive either. It's a class of problems that has polynomial verifiers of solutions. Second, NP-hard means the problem is either NP-complete or not in N…

So, NP-hard means that it's either NP-complete (the hardest NP can get), or even harder than that. Pretty intuitive to me.

Re: NP-hard does not mean hard (2017)

#48

Post by globular-toast »

tetha wrote: post #23
lambda wrote: post #7

Corollary: P does not mean easy. Most things that you do on the computer, you want to be O(n) or less; maybe O(n log n) or even O(n log^x n), but no slower than that. That means if you get a bigger problem, you can generally just get a proportionally bigger computer and be all set. Now, sure, there are plenty of O(n^2) problems where the n stays small enough, or you don't mind waiting or spending a ton of money on it…

Our CS-Prof also had another interesting point: P = NP could be true without changing many things in reality. This could occur if the reduction of an NP-complete problem onto a polynomial problem results in a runtime of such monstrous polynomial degree that the exponential algorithms are just faster for every tractable problem size. Something like this exists in some graph algorithms - theoretically faster algorithms…

This is similar to Knuth's reasoning for P=NP. Essentially there might be algorithms for these problems that are simply so complex that we might never know them.

Re: NP-hard does not mean hard (2017)

#49

Post by globular-toast »

vsnf wrote: post #5

Despite having done my undergrad in CS, I never understood what NP-hard really meant. I mean yeah, polynomial time, boolean logic, general-case not specific-case, transformable into other NP problems, I get it, but like, I don't get it? Anyway, after reading this article I feel like I've gotten one small step closer to filling in this gap in my CS knowledge.

You should grab a textbook about NP-completeness like Garey and Johnson. It's actually quite easy to understand and you can follow along some proofs for NP-completeness even if you don't have experience with that. NP-hard will follow.

Re: NP-hard does not mean hard (2017)

#50

Post by ngruhn »

Traveling salesmen is even solved to optimality (no heuristics) for pretty large instances with integer programming techniques.

Also SAT is pretty much a solved problem. With algorithms like CDCL.

This really surprised me. I also left my first complexity theory course believing that NP-hard = "not solvable in practice“

Post reply on HN