Short version: In what programming jobs would I see NP-Complete problems? The other night I got a chance to see Mark-Jason Dominus live. He was talking about NP-Complete problems informally after the presentation. NP-Complete problems have these characteristics:
No known efficient solution
Generally, a solution for one NP-Complete problem could be used to solve all NP-Complete problems
These are problems like the Travelling Salesman problem (find the least expensive route which goes through all cities a salesman must visit). The interesting thing was that NP-Complete problems could be "solved" by standard algorithms if you were willing to accept sub-optimal behavior. It's generally only in extreme cases that the conventional means would not work. My question for Mark was, in what programming job will I see problems like this? I asked it because I want to see interesting problems. Currently I'm a Business Intelligence programmer (read: glorified Visual Basic programmer), so I see no interesting problems. Mark's answer talked about the logistics of packing airplanes, integrated chip design, etc. But I want to know what type of programmers regularly see NP-Complete problems? Thanks in advance.
NP-Complete problems is not something you want to see at work. Real programmers should be aware of NP-c problems only so that they could avoid this problems and not get involved in solving them. The best one can do is to search for approximate solution. For this reason you might get impression it is hard to encounter this problems, but this is not true. This problems are everywhere, however software evolves steering away from this problems. If you really want to play with NP-c problems you should look at SATISFIABILITY problem or even better at SATISFIABILITY 3 (SAT3) problem which is quite easy to understand. Solving SAT3 is equivalent of solving all NP-c problem, because all NP-c can be reduced to SAT3.
Although I've seen some pretty ludicrous skill demands in the adverts over the last 2 years, "Must Be Able to solve NP-Complete problems" has yet to appear. Then again, I haven't been reading "Help Wanted at MIT"
An IDE is no substitute for an Intelligent Developer.
I was going to say what Mark said. So the answer is, programmers who have to solve these problems. Of course, most programmers at larger comapnies (e.g. airlines) don't have to solve these problems. Instead the company will employ Operations Management PhDs who figure out the solution and then give it to the trained monkey, excuse me, programmer, to write up. If you want to be approximating solutions to those problems, you need to get involved in a smaller company which uses developes to help with the domain specific problems. --Mark
Joined: Dec 04, 2000
Coincidentally, a frined of mine has her PhD thesis defense tomorrow, "Approximation algorithms for Combinatorial Optimization Under Uncertainty". From the abstract for her defense:
In the thesis we study a number of different scenarios of planning under uncertainty motivated by applications from robot navigation, communication network design and other areas. We develop approximation algorithms for several NP-hard stochastic combinatorial optimization problems in which the input is uncertain... The first problem we consider is motivated by a robot navigation application. The goal is to specify a route for robot to follow so as to maximize the value of packages successfully delivered subject to an uncertainty in the robot's lifetime. Another problem studied is concerned with designing a routing network under a probabilistic distribution of clients to be connected to a central server. Finally, we examine stochastic versions of several classical combinatorial optimization problems (including bin-packing, vertex cover, and others) in the context of a recourse framework, in which one can "plan ahead" based on limited information about the problem input, or "wait and see" until the entire input becomes known, albeit incurring additional expense.
In what programming jobs would I see NP-Complete problems I see several possibilities, but an obvious one is writing a software for UPS or any other company that is in the delivery logistics business. This is directly reminiscent of the traveling salesman problem.
Algorithmics is the systematic study of the design and analysis of algorithms. It deals with such fundamental questions as: How do we go about designing an algorithm for a given problem?, Is the algorithm correct?, Does it perform efficiently?, and Is it the best possible for the job?. Algorithms form the soul of Computer Science, and consequently the study of algorithms is a fundamental activity of the Computer Scientist. Greedy algorithms, divide-and-conquer, dynamic programming, graph techniques, and probabilistic algorithms. There are Limits on the power of computers because there are many problems where an efficient solution is unlikely to exist. These limits are provided by the Theory of NP-completeness.
BEA 8.1 Certified Administrator, IBM Certified Solution Developer For XML 1.1 and Related Technologies, SCJP, SCWCD, SCBCD, SCDJWS, SCJD, SCEA,
Oracle Certified Master Java EE 5 Enterprise Architect
Actually, I designed on a Newton app several years back that was of that stripe. It would allow you to log prices of commonly-purchased items and stores and used linear programming to organize shopping expeditions. It was a little ambitious, as it turned out. Data capture was too much of a hassle. Instead I'm using an inexpensive Palm shopping list program and I attach notations to the list when items go on sale or I notice an expecially good price somewhere.
Originally posted by Tim Allen: Mark's answer talked about the logistics of packing airplanes, integrated chip design, etc. But I want to know what type of programmers regularly see NP-Complete problems?
My two cents: researchers in artificial intelligence research centres are probably the people who encounter NP-completeness most frequently. But unfortunately/fortunately, almost all of the really "interesting" AI problems lie in the range of NP-Completeness without question, that is to say, our current Church-Turing/von Neumann computing modell and the NP-theory system are just too wide/loose to direct the practices in real world. The result is that, a programmer, even a senior developer can still do his job well without well knowing the NP theory(NP theory != algorithm); In another perspective, for Quanto-Computing and other modern computing modells, Church-Turing/von Neumann modell and NP theory are too narrow/weak to direct/support the practice. So, if you are not going to pursuit a phD in computer science or you are not preparing for an exam( like me ), don't worry too much about it. Being aware of some import conclusions is enough to help you gain understanding to advanced practical algorithms. Probably the development our computing theory is still in her pre-Newton era, serious computer scientists have still too much unknown to reveal. Regards, Ellen
Timothy Chen Allen
Joined: Mar 16, 2003
Originally posted by Ellen Zhao:
So, if you are not going to pursuit a phD in computer science or you are not preparing for an exam( like me ), don't worry too much about it. Being aware of some import conclusions is enough to help you gain understanding to advanced practical algorithms.
Thanks everyone for your responses. Let me explain why I'm interested in this (get out your hankies, this is a sad story ): I got my Comp Sci degree in 86 from the Naval Academy. I had enjoyed "G�del, Escher, Bach" by Douglas Hofstadter, so I studied a concentration in AI. I loved programming, implementing algorithms, trying to analyze algorithms, etc. I wrote cool AI programs. I thought about algorithms. After my stint in the Marines and two years in Peace Corps, I got an entry level job as a programmer. I started doing database front ends in Visual Basic. It was fun, but I noticed there wasn't much thinking about algorithms. I expected this to change as I advanced. Eventually I showed some talent for database programming and got picked up by Oracle. They put me in their Business Intelligence practice. I spent four years flying around implementing BI. It was fun, but I noticed there wasn't much thinking about algorithms. (Repeat scenario a few more times...) Finally, I'm in Spain as an ERP/BI specialist. I hardly ever write programs for my work now. I'm good at what I do. It's not fun. There's no thinking about algorithms. I feel I've gone wrong somewhere. I'm studying Java, Extreme Programming and Genetic Algorithms on my free time, now. I want to make the leap to another job, in or out of Spain, but this time I want to program and think about algorithms. Now that I've said all that, where should I try to find work? Thanks in advance.
Well, not to dampen your parade, but outside of a pure research environment, don't expect to be spending more than 10-20% of your time on the "fun" stuff - the supporting infrastructure will take up most of the rest. Back before we had "IT", there was "Data Processing". Algorithmically-speaking it was nothing to get excited about. Counting, tabulating, moving items around in ledgers, etc. Business can't run without it, but it's not what I'd call intellectually demanding. However, even back then there were diversions - specialized sorts, compressions, compilers, hashes, and more. The best place (outside of academia) to be involved in such refinements back then was in the area of mainframe Systems Programming. Although many of the old challenges are now best served by canned solutions, there is no shortage of replacements. We still are looking for newer and better graphics algorithms, optimal traffic routing (not only network, but on the motorways!), improved man-machine interfaces and many more. My own best recommendation is to go to the local bookstore, bring home a few armloads of tech magazines (and while you're at it, things like Discover, Popular Science, Scientific American, New Scientist, etc.) and see what they're talking about that excites you. Then see what it takes to get involved. And, of course, if academia is your bent, MIT really does have a thing on "NP-complete" if my MIT Press book on algorithms is any indication.
Joined: Dec 04, 2000
I agree with Tim H, go into research. You might enjoy getting a PhD and going into academia. You may just want to work in research group at a college. You could also work for firms known to emphasize R&D (e.g. IBM). I recommend Introduction to the Theory of Computation by Michael Sipser. I took both his complexity theory classes at MIT and found him to be a great teacher. In fact, he was using a draft of the book as a working text when I took it (read the acknowledgements, you may recognize a few names ;-). --Mark
Hi Tim A, My response may off tangent, there is a company outthere utilizing AI into business intelligent with emphasis more into security. The link originates from HS Thomas. http://www.searchspace.com See if you could find something useful for your case. Regards, MCao