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

21–30 of 101 posts

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

#21

Post by raincole »

quickthrower2 wrote: post #12
jandrese wrote: post #9

Earlier quoted context omitted.

From what I remember: NP: Finding the solution takes more than polynomial time, but you can verify the answer is correct in polynomial time. NP-Hard: Finding the solution takes more than polynomial time, and it also takes more than polynomial time to verify that the solution is correct. NP-Complete: NP-Hard, but it can be transformed into any other NP-Complete problem in polynomial time. This is special because it me…

--Edit: this was wrong, see reply comment-- NP: you can verify the answer is correct in polynomial time. (and no other clauses) Anything in P is in NP

> --Edit: this was wrong, see reply comment--

You're not wrong tho. NP problems can be verified in polynomial time.

Nondetermisitic turnig machine is like a turing machine that has multiple "next steps" instead of one at a given time, and can migically choose the correct next step.

You can think it as "taking all the possible paths at the same time (but at the end only the correct one matters)". But you can also think it as "given all the 'choices' it made, check if there is actually such a path", in other words, verifying a certification.

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

#22

Post by minitech »

earth2mars wrote: post #20
jandrese wrote: post #9

Earlier quoted context omitted.

From what I remember: NP: Finding the solution takes more than polynomial time, but you can verify the answer is correct in polynomial time. NP-Hard: Finding the solution takes more than polynomial time, and it also takes more than polynomial time to verify that the solution is correct. NP-Complete: NP-Hard, but it can be transformed into any other NP-Complete problem in polynomial time. This is special because it me…

[flagged]

Is this a generated answer?

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

#23

Post by tetha »

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 exist, but in practice, they are a lot slower than the theoretically slower algorithm until completely silly graph sizes.

This could turn even more frustrating if the proof was nonconstructive.

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

#24

Post by zer8k »

jandrese wrote: post #9
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.

From what I remember: NP: Finding the solution takes more than polynomial time, but you can verify the answer is correct in polynomial time. NP-Hard: Finding the solution takes more than polynomial time, and it also takes more than polynomial time to verify that the solution is correct. NP-Complete: NP-Hard, but it can be transformed into any other NP-Complete problem in polynomial time. This is special because it me…

I don't think the downvotes here are fair given the corrections this person has received. These misconceptions are wildly common. I'm sure 90% of the downvoters couldn't even accurately identify this stuff.

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

#25

Post by fooker »

s1dev wrote: post #18
fooker wrote: post #15

Earlier quoted context omitted.

Interestingly being P complete has another unexpected consequence: it means your problem is going to be difficult to parallelize. This is why parallel SAT solvers are barely faster than the usual ones. SAT is NP complete, but a crucial step in SAT solving (unit propagation) is P complete.

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).

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

#26

Post by Cerium »

s1dev wrote: post #18
fooker wrote: post #15

Earlier quoted context omitted.

Interestingly being P complete has another unexpected consequence: it means your problem is going to be difficult to parallelize. This is why parallel SAT solvers are barely faster than the usual ones. SAT is NP complete, but a crucial step in SAT solving (unit propagation) is P complete.

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)

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 the class NC, which consists of those problems which can be efficiently solved on a parallel computer. This is because parallel computers can be simulated on a sequential machine. It is not known whether NC = P. In other words, it is not known whether there are any tractable problems that are inherently sequential. " From: https://en.m.wikipedia.org/wiki/P-complete

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

#27

Post by zer8k »

viknesh wrote: post #14
jandrese wrote: post #9

Earlier quoted context omitted.

From what I remember: NP: Finding the solution takes more than polynomial time, but you can verify the answer is correct in polynomial time. NP-Hard: Finding the solution takes more than polynomial time, and it also takes more than polynomial time to verify that the solution is correct. NP-Complete: NP-Hard, but it can be transformed into any other NP-Complete problem in polynomial time. This is special because it me…

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.

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

#28

Post by adalacelove »

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…

Staying in the realm of polynomial complexity matrix multiplication comes to mind, where we are approaching more and more O(n^2), where O(n^3) is the naive, but more common implementation.

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

#29

Post by fooker »

Cerium wrote: post #26
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)

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.

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

#30

Post by Tainnor »

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.

> 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.

Yes. This definition is equivalent to the one about being verifiable in polynomial time, since your non-deterministic TM can just have a different branch for every possible verification "oracle".

> I think the more practical definition is "not polynomial"...lol.

Well, there are non-polynomial algorithms harder than NP. If a solution can't even be verified efficiently, for example.

Post reply on HN