Hacker News new | ask | show | jobs
by red75prime 2725 days ago
If the halting problem was merely NP complex, it would have still limited practical possibilities of static analysis.
1 comments
adrianN 2725 days ago
Eh, modern SMT solvers are very practical tools, as are solvers for Mixed Integer Linear Programs. NP-completeness doesn't mean that you can't solve most instances you care about in reasonable time.
link
red75prime 2725 days ago
Yes. And the halting problem doesn't preclude static program analysis even if it works with only a subset of all possible programs.
link
adrianN 2725 days ago
It looks like we're in perfect agreement then.
link