|
|
|
|
|
|
by matklad
1207 days 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. |
|
|