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

11–20 of 101 posts

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

#11

Post by Ar-Curunir »

[deleted] wrote: post #6
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.

[deleted]

For cryptography, every instance is (conjectured to be) complex, not just laborious.

For worst-case NP-hardness, the complex instances are also laborious, while the simple instances are not laborious.

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

#12

Post by quickthrower2 »

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…

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

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

#13

Post by dwattttt »

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

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

#14

Post by viknesh »

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…

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.

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

#15

Post by fooker »

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…

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.

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

#16

Post by raincole »

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…

^ The most common misconceptions about NP/NP-Complete/NP-Hard, packed in one comment!

But seriously for anyone reading this, please refer to the other sibling comments.

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

#17

Post by Dylan16807 »

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

I think it's worth saying what NP stands for.

Nondeterministic Polynomial. Where "nondeterministic" basically means you get to try every single polynomial solution in parallel.

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

#18

Post by s1dev »

fooker wrote: post #15
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…

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)

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

#19

Post by minitech »

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

Not wrong, just a different criterion that describes the same complexity class.

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

#20

Post by earth2mars »

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…

[flagged]
Post reply on HN