Is it usually linear to reduce other NP-complete problems to SAT? | Hacker News

Hacker Newsnew | past | comments | ask | show | jobs | submit

		kizer on Sept 28, 2017 \| parent \| context \| favorite \| on: Gophersat: A SAT solver written in Go Is it usually linear to reduce other NP-complete problems to SAT?

rw on Sept 28, 2017 [–]

No, polynomial time. For reference, see these Wikipedia pages:

https://en.wikipedia.org/wiki/Polynomial-time_reduction

https://en.wikipedia.org/wiki/Karp%27s_21_NP-complete_proble...

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact