Such is the nature of NP Complete problems, like SAT. They are the most general ... | Hacker News

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

		kqr on July 31, 2020 \| parent \| context \| favorite \| on: Kissat SAT Solver Such is the nature of NP Complete problems, like SAT. They are the most general versions of NP problems, and all NP problems can be phrased as any NP Complete problem. I don't know if there's an established formalised terminology for this type of conversion, and I haven't found one from a quick web search. But look up something like "translate", "convert", "reduce", "encode", or the like in conjunction with "NP Complete" and you shall find what you are looking for.

tgflynn on July 31, 2020 [–]

> I don't know if there's an established formalised terminology for this type of conversion

Technically they're polynomial-time many-one reductions.

https://en.wikipedia.org/wiki/Many-one_reduction

But in practice I think people usually just call them "reductions".

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