5 ms·
The other way around: to prove that X is NP-complete you need to reduce SAT(or any other known NP complete problem) to X. The intuition here is that if you hav
by matklad 4y ago
The other way around: to prove that X is NP-complete you need to reduce SAT(or any other known NP complete problem) to X.
The intuition here is that if you have a magic algorithm which solves X efficiently, you should be able to use this algorithm to solve any other NP problem, like SAT.