Comment

Comment by memkit

I agree with you, I just think the condition "being in NP" is needlessly confusing. The whole point is that you can always find a reduction from easier problems to harder ones. It just so happens that NP encompasses all the problems easier than SAT.

The reason why your statement is confusing to me is that if you generalize it beyond NP, it breaks down; for an arbitrarily hard complexity class M and an arbitrary M-hard problem, you don't need to be in M to be able to find a reduction to the M-hard problem.

parent memkit 1 year ago

Discussion

Live from the official Hacker News API

A modern reader for Hacker News · SvelteKit + Skeleton