undefined | Better HN

0 pointsbutokai1y ago0 comments

Add to this that propositional logic (the language in which we express SAT) is a versatile language to code problems in. Finding cliques in a graph is also NP complete, but it is less natural to use it as a language to code other problems.

0 comments

2 comments · 1 top-level

riku_iki1y ago· 1 in thread

> Add to this that propositional logic (the language in which we express SAT) is a versatile language to code problems in

is it though? You can't express some basic loop in propositional logic, right?

viraptor1y ago

Loops are part of a coded solution, not the problem. With SAT you encode the problem / solution space itself.

j / k navigate · click thread line to collapse