Comment

Comment by Tyr42

You can prove something is in NP by providing a (polynomial) reduction from a known NP hard task, and vice versa. All the known NP problems (Knapsack, SAT, etc) are mutually reducable in this way, so solving one lets you solve the others. So if X was shown to be NP, then given a polynomial time solution to X, you can stack the polynomial time reduction from X to SAT to solve SAT in polynomial time too.
parent Tyr42 3 months ago

No comments yet

Be the first to share your thoughts.

Live from the official Hacker News API

A modern reader for Hacker News · SvelteKit + Skeleton