3 ms·
Is it usually linear to reduce other NP-complete problems to SAT?
by kizer 9y ago
Is it usually linear to reduce other NP-complete problems to SAT?
- rw 9y agoNo, polynomial time. For reference, see these Wikipedia pages: https://en.wikipedia.org/wiki/Polynomial-time_reduction https://en.wikipedia.org/wiki/Polynomial-time_reduction https://en.wikipedia.org/wiki/Karp%27s_21_NP-complete_problems https://en.wikipedia.org/wiki/Karp%27s_21_NP-complete_proble...