|
|
|
|
|
by tikhonj
2674 days ago
|
|
SAT solvers only scale sometimes. Complexity theory is a starting point for understanding why this "sometimes" is inevitable, but it never even implies that NP-complete problems are never tractable. Complexity theory gives us an understanding of how powerful and expressive SAT is which very much does inform real development. Arguing that "SAT is NP-complete and therefore useless" is not misusing complexity theory, it's misunderstanding complexity theory—not misunderstanding some deep result or non-trivial consequence of complexity theory, but misunderstanding the fundamentals that are covered in the first lecture of the first class on the topic. |
|
We did learn the definitions but "worst case" was never highlighted as such, it was naturally assumed. The closest we got was the discussion that constant factors may matter for small problems and O analysis masks those differences.