4 ms·
If the halting problem was merely NP complex, it would have still limited practical possibilities of static analysis.
by red75prime 8y ago
If the halting problem was merely NP complex, it would have still limited practical possibilities of static analysis.
- adrianN 8y agoEh, 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.
- red75prime 8y agoYes. And the halting problem doesn't preclude static program analysis even if it works with only a subset of all possible programs.
- adrianN 8y agoIt looks like we're in perfect agreement then.