File APIs for Java Developers
Manipulate DOC, XLS, PPT, PDF and many others from your application.
http://aspose.com/file-tools
The moose likes Jobs Discussion and the fly likes NP-Complete problems and programming jobs Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Careers » Jobs Discussion
Bookmark "NP-Complete problems and programming jobs" Watch "NP-Complete problems and programming jobs" New topic
Author

NP-Complete problems and programming jobs

Timothy Chen Allen
Ranch Hand

Joined: Mar 16, 2003
Posts: 161
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.


    Timothy Chen Allen
    Learn Spanish in Washington, DC
    Jason Menard
    Sheriff

    Joined: Nov 09, 2000
    Posts: 6450
    I'm going to move this to Jobs Discussion.
    stara szkapa
    Ranch Hand

    Joined: Mar 27, 2003
    Posts: 321
    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.
    Tim Holloway
    Saloon Keeper

    Joined: Jun 25, 2001
    Posts: 15641
        
      15

    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"


    Customer surveys are for companies who didn't pay proper attention to begin with.
    Mark Herschberg
    Sheriff

    Joined: Dec 04, 2000
    Posts: 6037
    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
    Mark Herschberg
    Sheriff

    Joined: Dec 04, 2000
    Posts: 6037
    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.

    Hopefully that will help generate some ideas.

    --Mark
    John Smith
    Ranch Hand

    Joined: Oct 08, 2001
    Posts: 2937
    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.
    Billy Tsai
    Ranch Hand

    Joined: May 23, 2003
    Posts: 1297
    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
    Tim Holloway
    Saloon Keeper

    Joined: Jun 25, 2001
    Posts: 15641
        
      15

    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.
    Ellen Zhao
    Ranch Hand

    Joined: Sep 17, 2002
    Posts: 581
    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
    Ranch Hand

    Joined: Mar 16, 2003
    Posts: 161
    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.
    Tim Holloway
    Saloon Keeper

    Joined: Jun 25, 2001
    Posts: 15641
        
      15

    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.
    Mark Herschberg
    Sheriff

    Joined: Dec 04, 2000
    Posts: 6037
    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
    Matt Cao
    Ranch Hand

    Joined: Apr 03, 2003
    Posts: 715
    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
     
     
    subject: NP-Complete problems and programming jobs
     
    Similar Threads
    Table Oriented Programming
    Permutation help
    What impedence mismatch?
    Plotting points for a polygon
    Certification vs. Degree