Hacker News
points by sourdecor 3 days ago | 0 comments
"Any NP complete problem can be changed into 3SAT in polynomial time" - if I remember correctly, turning an NP-complete problem into 3SAT is not part of the problem statement - it just means that when working with NP-complete problems, they are always translated to 3SAT first, and whenever someone is trying to prove something they are working against 3SAT.
[–] gbacon 2 days ago
The class NP-complete contains the hardest problems in NP. If you pick any problem in NP-complete, all problems in NP can be reduced to it (meaning that a solution to the problem you chose can be used to solve everything in the rest of NP) in polynomial time or “efficiently.” This applies to all of NP, including every other NP-complete problem, so in a sense, NP-complete problems are the same problem dressed in different clothing.

So the reduction to 3SAT could happen in principle, but it isn’t a necessary step.

Hacker News