Tweeted twitter.com/StackCompSci/status/866462709667291136
2 edited tags
| link
    Post Migrated Here from stackoverflow.com
1
source | link

Why is NP-hard not necessarily NP?

A problem X is NP-hard if every problem in NP can be reduced to X. But every problem in NP has a polynomial time verification algorithm, so then does that not mean that I can also verify X in polynomial time because every NP problem is reducible to X? Can someone please explain or give an example.