News for hackers. Stuff that matters.
Re:The Halting Problem is a terrible example of NP-Harder by johanvts on Thursday April 17, 2025 @06:19AM (#43714905)
> NP-hard is the set all problems at least as hard as NP-complete

Im a bit confused by this. I thought NP-complete was the intersection of NP-hard and NP. Maybe this is stating the same?

Re:The Halting Problem is a terrible example of NP-Harder by redleader55 on Thursday April 17, 2025 @06:38AM (#43715007)
This [1] diagram from Wikipedia represents you are saying in a visual way. NP-hard and NP-complete are defined as basically an equivalence class modulo an algorithm in P which transforms from one problem to the other. In more human terms both NP-hard and NP-complete are reducible with a polynomial algorithm to another problem from their respective class, making them at least as hard.

The difference between the two classes, again in human terms, is that NP-complete problems are decision problems "Does X have property Y?", while NP-hard problems can include more types - search problems, optimization, etc, making the class NP-hard strictly larger than NP-complete in set terms.

The statement in the article means that NP-hard problems require solving a NP-complete problem plus a P problem - hence being at least as hard.

[1] https://en.m.wikipedia.org/wiki/File:P_np_np-complete_np-har...

Re:The Halting Problem is a terrible example of NP-Harder by zahlman on Thursday April 17, 2025 @12:22PM (#43719030)
If NP-hard isn't even a subset of NP, why is it called "NP-hard"?
Re:The Halting Problem is a terrible example of NP-Harder by sfink on Thursday April 17, 2025 @03:39PM (#43721218)
Membership in NP is a statement about how easy a problem is (specifically, that you can verify an answer in no worse than polynomial time). NP-hard is about how hard a problem is (at a minimum).

I wonder if there would be less confusion over this if NP had been called "NP-easy" in the first place. But Wikipedia says that by now that term has already been taken.

P is "very easy": you can solve these in polynomial time. NP is "easy": you can verify a solution in polynomial time. Are there any problems you can verify but not solve in polynomial time? Nobody knows! (But ~everyone thinks so.)

NP-hard is "hard": it takes polynomial time or more to even verify these.

Re:The Halting Problem is a terrible example of NP-Harder by suzumer on Thursday April 17, 2025 @02:42PM (#43720641)
Because a language being NP-hard implies it is at least as hard as the hardest NP problems. For any language that is NP-hard, if one had a turing machine that decided the language, one could construct a polynomial time transformation of any language in NP to the NP-hard language to decide it using the NP-hard turing machine.
Re:The Halting Problem is a terrible example of NP-Harder by Sharlin on Thursday April 17, 2025 @03:42PM (#43721269)
Because naming things is one of the two difficult problems in computer science.
Re:The Halting Problem is a terrible example of NP-Harder by edanm on Thursday April 17, 2025 @05:22PM (#43722363)
I don't believe this is accurate.

The difference between NP-Hard and NP-Complete is that NP-Complete problems are both NP-Hard, and in NP. As opposed to NP-Hard problems that are not NP-Complete, meaning they are not themselves in NP.

Re:The Halting Problem is a terrible example of NP-Harder by Khoth on Thursday April 17, 2025 @09:31AM (#43716558)
NP-complete is indeed the intersection of NP-hard and NP.

If you can solve any NP-hard problem then you can solve any NP-complete problem (because you can convert any instance of an NP-complete problem to an NP-hard problem), so NP-hard problems are "at least as hard" as NP-complete problems.

(But an NP-hard problem might not be in NP, ie given a purported solution to an NP-hard problem you might not be able to verify it in polynomial time)