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

31–40 of 101 posts

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

#31

Post by gdprrrr »

dwattttt wrote: post #13
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…

A terrific teardown of tracking down an unexpected O(n^2): https://randomascii.wordpress.com/2021/02/16/arranging-invis...

Also reminds me of the GTA online case.

https://news.ycombinator.com/item?id=26296339

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

#32

Post by dandanua »

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 NP at all. Which is another confusing naming, because problems not in NP are NP-hard.

As a saying goes, there are two main problems in programming - naming things and cache invalidation. And in this case the former fails badly.

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

#33

Post by gnull »

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.

Cerium is correct, we don't know if P is efficiently parallelizable.

Is there a formal proof of what you're talking about that we can read?

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

#34

Post by fooker »

gnull wrote: post #33
fooker wrote: post #29

Earlier quoted context omitted.

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.

Cerium is correct, we don't know if P is efficiently parallelizable. Is there a formal proof of what you're talking about that we can read?

Are you perhaps confusing P with P complete?

https://www.researchgate.net/profile/Walter-Ruzzo/publicatio...

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

#35

Post by Skeime »

zer8k wrote: post #27
viknesh wrote: post #14

Earlier quoted context omitted.

NP: Checking a solution takes polynomial time. NP-Hard: "The problem is at least as hard as any problem in NP." Basically, if X is an NP hard problem and you are given an oracle to solve X, you can solve any problem in NP by first transforming it to an instance of X and then solving it. NP Complete: The problem is NP Hard & in NP.

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.

“Not polynomial” is an easy trap to fall into (and one I have fallen into) but it’s really not correct. All polynomial-time problems are also NP problems (P=NP is about whether the converse is true, and if P=NP, all problems in NP are actually polynomial-time). So even if talking to a layman, saying that NP is non-polynomial is really missing the point of the question.

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

#36

Post by gnull »

fooker wrote: post #25
s1dev wrote: post #18

Earlier quoted context omitted.

Is there some good intuition why P-complete problems are difficult to parallelize? This is the first I've heard of it (but then again, I'm usually interested in more obscure complexity classes)

Yes, linear(-ish) dependency chains so that your threads have to wait for one thread to provide a result (infinitely often).

Are you stretching "this specific strategy for parallelizing P that I came up with won't work" to "there's no way to parallelize P"?

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

#37

Post by beefield »

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 philosophical issue of not being able to prove a negative, you really can't prove that there is not a way to solve a problem fast.

2. That obviously P!=NP. You just for example lose information before giving the problem to the solver, say, I'm thinking a float with n decimals, then I round it to nearest integer and ask you to find the float given the integer. I can check the guess in linear time as n increases, but your difficulty increases exponentially as n increases.

I am pretty sure there is something in this problem that makes it a not legal P/NP problem, but I have no idea what. I have a couple of times tried to look for more formal definitions of P/NP, but the jargon goes immediately above my head.

(The "guess" is admittably there a bit informal, if you want a bit more formal problem, you take a process C that is mathematically proven to be sufficiently sensitive to initial conditions (e.g. chaotic), take integer x and calculate y = C(x), round y and ask what's x.)

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

#38

Post by fooker »

gnull wrote: post #36
fooker wrote: post #25

Earlier quoted context omitted.

Yes, linear(-ish) dependency chains so that your threads have to wait for one thread to provide a result (infinitely often).

Are you stretching "this specific strategy for parallelizing P that I came up with won't work" to "there's no way to parallelize P"?

It’s more like : you win a Turing award by finding a strategy to parallelize this problem as you’ll be able to use that approach to parallelize all problems in P, proving NC = P.

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

#39

Post by withinboredom »

In my experience, solving the NP-hard problem isn't the part that is hard, it's reducing the problem space and/or solution space to make it into a P-problem (when n is sufficiently big enough to worry about it).

For example, changing how you're storing the data in the first place, or talking to PM/PO's to learn if you really need an exact solution or if a very close approximation is ok.

Sometimes, you're even trying to solve this problem while n has grown over months or years, and some customers are hitting the tipping point and the app is crashing. So there's a lot of pressure to perform.

That's what makes np-hard problems hard, imho; not the problem itself, but all the bullshit to get rid of it.

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

#40

Post by jsolson »

zer8k wrote: post #27
viknesh wrote: post #14

Earlier quoted context omitted.

NP: Checking a solution takes polynomial time. NP-Hard: "The problem is at least as hard as any problem in NP." Basically, if X is an NP hard problem and you are given an oracle to solve X, you can solve any problem in NP by first transforming it to an instance of X and then solving it. NP Complete: The problem is NP Hard & in NP.

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 essence of the equivalence between being able to solve problems in NP in polynomial time on a (hypothetical) non-deterministic Turing machine and being able to deterministically verify a solution to those problems in polynomial time.

Post reply on HN