Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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?

share|improve this question
1  
My impression is that for things like the traveling salesman problem, one ditches the exponential time algorithm, and instead goes with a much better heuristic (in the case of the traveling salesman, they are quite good) –  soandos May 31 '12 at 5:03
    
Lots of problems are solved with "exponential" algorithms. (TSP, CDS, ILP, etc.) It's just that the exponential algorithms happen to have good heuristics, so they work reasonably with lots of real-world data. A better question might perhaps be, "How common are generic-case exponential-time algorithms in production software?" –  Mehrdad May 31 '12 at 5:30
    
Adjusted the question –  World Engineer May 31 '12 at 5:43
    
Traveling salesman is n!, not exponential. –  user281377 May 31 '12 at 9:09
1  
@user281377: It is also in O(n^2 2^n) so yea, it's an exponential problem. This is also clear because it can be mapped to SAT in poly time which can be solved in 2^n time -- that works for all NP problems. –  Raphael May 31 '12 at 9:48
show 4 more comments

4 Answers

up vote 5 down vote accepted

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.

share|improve this answer
add comment

Let me take the example of travelling salesman problem. I have worked on it a few times.

There are a few times when I have been in a team that wrote solution for travelling salesman problem but with some more parameters. For example, it could be a store with a fleet of technicians and engineers each with a unique skill set. The destinations come up every day in the form of service requests. All the programs are in production though they have undergone modifications and maintenance since originally writing them.

This is how they worked. Each engineer would receive a list of things to service on a hand held device everyday. As they finish each service task, they should close the case. The cases that are left out join the cases to be scheduled for the following day with slightly higher priority as by then the customer would have expressed some dissatisfaction. There was a large set of reasons why an engineer would not attend a case. Traffic problems were most common.

How common are they? At least as common as number of after sale service requests coming from customers. Without after sale service, for example, retaining customers is going to be hard and gaining new ones is going to be harder.

With many web based shops such as Amazon and other book stores and other such shops doing well in business, I would think travelling salesman is more common than it used to be. Also, there could be many variations of the travelling salesman problem that are taught in text books.

share|improve this answer
    
Like the Canadian traveler. –  soandos May 31 '12 at 6:27
add comment

Commonly used algorithm with exponential worst case complexity is the simplex method used in linear programming. However, what is generic-case complexity of that method is an open issue. With some specific assumptions it's polynomial.

share|improve this answer
add comment

Programming language interpreters are worse than exponential time (in the length of their input, i.e. in the length of the program they're interpreting), and they are quite common. Another example is automatic theorem proving / constraint solving / sat solving / integer linear programming. And yet another example is symbolic differentiation as implemented in e.g. Maple/Mathematica (although it is possible to do symbolic differentiation in linear time if you're allowed to share subexpressions between nodes).

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.