←back to thread

The Halting Problem is a terrible example of NP-Harder

(buttondown.com)
108 points BerislavLopac | 1 comments | 17 Apr 25 07:34 UTC | HN request time: 0s | source
Show context
johanvts ◴[17 Apr 25 10:19 UTC] No.43714905[source]▶
> 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?

replies(2): >>43715007 #>>43716558 #
redleader55 ◴[17 Apr 25 10:38 UTC] No.43715007[source]▶
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...

replies(2): >>43719030 #>>43722363 #
1. edanm ◴[17 Apr 25 21:22 UTC] No.43722363[source]▶
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.