I know that exponential time algorithms should generally be avoided but are sometimes necessary. A case being the Traveling Salesman. How common are such algorithms in production software? Are these cases typically necessary or a result of rush jobs? I understand that many can be solved with a good heuristic. What is typically done with those that cannot?
How common are generic-case exponential time algorithms in production software?
algorithms
Something that not in production software but done on production software is formal verification. It is probably not adopted for most customer software but gains track for embedded systems and drivers, that is for hard- and software whose correctness is important (and tractable).Those verficiation problems that are actually computable (barrier #1) are often EXPTIME-hard, in the more lucky cases you get PSPACE-complete problems (barrier #2). Both classes are (suspected to be) harder than NP-complete problems, which are easy in comparison. Doubly-exponential problems are also easily obtained.In these cases, heuristics (in the sense of end result) don't cut it as you need definite results; therefore you need big machines and time. There are heuristics (in the sense of alternative selection) that often lead to shorter runtime (i.e. clever search space exploration when error states are searched) but in the worst case, waiting is all you can do. Or you can do a pen-and-paper proof and have it checked by machines, which is computationally simpler.