The importance of complexity

This topic was created by Julian Bradfield .

  1. Julian Bradfield

    The importance of complexity

    In a vigorous discussion about revising courses in a computer science degree, one of my colleagues opined that "every decent programmer is sometime going to come across a task that is NP-hard, so they need to know to tackle NP-hard problems".

    I'm curious as to whether anybody on here (who is a programmer after going through a so-called top university's CS degree) has ever been asked to solve a task that is computationally intractable, and if so whether they used the last couple of decades' work on such things to solve it.

    Come to that, how many CS graduates ever solve algorithmic problems, rather than systems engineering problems?

    1. Hungry Sean

      Re: The importance of complexity

      if you can make your problem look like a graph, it is pretty much assured that there's either a known polynomial time solution or it's np hard. The good thing about these kind of problems is there's no "right" answer, so you can take your pick from a variety of reasonably good heuristics.

      Fun example: was considering a while ago an AI for a turn based game where monster hordes would try to maneuver through the dungeon to cut off the free space available to the player with the hopes of eventually surrounding him in an indefensible area. So how do the monsters move to optimally cut down the fraction of the dungeon that can be reached?

      In professional work, I have generally tried to find approaches to problems that avoid getting into NP hard nasties. Simplifying the problem statement so that something in linear or log time works instead is good if you do work with real-time systems.

      Overall, I agree with the second poster-- even those engineers who do work with algorithms spend the majority of their time on unglamorous tasks-- plumbing, buffer management, refactoring, validation/verification, etc. A well written kernel is generally small and tractable, a production system typically is not. I think this may have something to do with why algorithmics get a lot more attention in our schools than software engineering. Frankly, I'm not convinced you can teach software engineering in an environment where everyone gets the same exact problem and is assessed objectively on individual performance. Building a big system is ultimately a group endeavor and possibly beyond the scope of a semester course.

    2. Daniel von Asmuth
      Boffin

      Re: The importance of complexity

      As you may guess, I was once asked to write a program that centered on the Travelling Salesman problem.

    3. Big Ron

      Re: The importance of complexity

      Most developers do not get to work on NP hard problems. I have been solving transportation work assignment problems using K-opt, insertion and genetic algorithms for the past 25 years, and I have had only one other person work on these algorithms with me. The huge majority of the other developers worked solely on the data manipulation end of the applications. It's a lot like compiler design, very people actually do that kind of work.

    4. Anonymous Coward
      Anonymous Coward

      Re: The importance of complexity

      I'm a programmer, and I went through CS at a so-called "top university" (one of the Russell Group). I still have my copies of Numerical Algorithms, the Aho dragon book and Knuth.

      I have worked in the NP-hard space in only a handful of occasions. I would say that the most important aspect is knowing how to recognize that a problem is NP-hard and being able to find acceptable solutions. So from a teaching perspective I would suggest that students understand graph theory pretty solidly and are familiar with some of the most common cases, such as packing problems and the bandwidth problem.

      Bear in mind that (especially in CS) there is a tension between teaching the students to be employable programmers and teaching them pure science. One sees this in the endless debates about whether they should be doing exercises in Java or something more "academic" like Modula-2 (I still have the scars) or Haskell. I think a reasonable compromise is to teach the fundamentals of NP-hard problem recognition and resolution and leave the advanced stuff to final-year undergrads taking the elective courses or first year grad students.

      1. Don Jefe

        Re: The importance of complexity @ AC 19:09

        I believe you've nailed the most important, but most poorly understood, part of these problems: Identifying acceptable practical solutions. There is a risk element involved that neither the calculator nor the developer are particularly well equipped to handle.

        I've worked with many smart people on very difficult problems and there seems to be a direct correlation between the logical capabilities of the individuals and the practicality of their proposed solutions: The 'smarter' the person, the dumber the solution. I realize that's a terrible generalization but in my experience it is generally (ha!) true.

        For better or worse, successfully identifying acceptable solutions requires the input of end users and operational level SME's who understand the practical implications of solutions. The SME's aren't required to understand the calculation level complexities of the problem beyond those used to define the metrics of success. Conversely the developers need to understand not only the calculation complexities of the problem, but actually understand the problem itself. A tough role to fill.

        The biggest challenge with NP-hard problems isn't the solution itself: It is communication. Getting two diametrically opposed types of thinking to converge in a useful manner. It isn't easy to do, as the social and hierarchical prejudices of both the developers and operational types weigh heavily on everyone. One group is a bunch of geeks, the other is a lot of idiots who don't understand why it's so hard to 'make the computer go'. Achieving harmonious communications is very difficult, but if done well, mitigates a lot of the complexities in a solution.

        1. What's this?

          Re: The importance of complexity @ AC 19:09

          The 'smarter' the person, the dumber the solution. So true!! "The problem is being solved by complex methods which actually needs basic ideas or just common sense."

          1. Anonymous Coward
            Anonymous Coward

            Re: The importance of complexity @ AC 19:09

            Oh my god.. I know... So true!!!

            Additionally, (referencing Don Jefe earlier in the thread) there is an element of posturing and ego involved. Some software designers I've come across pull out their ivy league credentials as though that's some invulnerability to criticism, when in fact it's more likely for them to stop learning as soon as they have been issued with a certificate.

            Since I don't care what people think of me and have little or no respect for basically anyone, I'm not afraid to burst bubbles and deflate egos if it gets a workable solution. Of course, I could go about things in an ordered politically correct way, but it takes too long and I think people are generally complacent and over-sensitive.

            There is no reason why a 1 line solution shouldn't be the answer required. Except the ivy leaguer says so! So I'm asked to make something more complicated just for the sake of it.

    5. Anonymous Coward
      Anonymous Coward

      Re: The importance of complexity

      Yes. Frequently.

    6. Ruli Manurung

      Re: The importance of complexity

      I would say that the vast majority of programmers never encounter NP-hard problems. In terms of algorithmic problems, most probably sorting and searching problems form the bread and butter cases.

      Most CS graduates in my neck of the woods end up doing enterprise information systems, which is where all the jobs are, and I would argue that knowledge of NP-hard problems is almost irrelevant (with the possible exception of those working in operations research).

      Don't get me wrong, I'm firmly on the side of advocating the teaching of CS as a scientific field, but the truth is that once they enter the real world, most of that stuff quickly becomes a distant memory.

      However, perhaps all this talk of the next wave of Big Data(TM) and Data Science(TM) and Predictive Analytics(TM) and whatnot will change the landscape somewhat in the near future...

    7. johnggold

      Re: The importance of complexity

      Since I deal with NP-hard programming daily, I cannot see the problem.

      What I do find is that many programmers struggle to remember anything they either learned at school or university, so problems are perceived as NP-hard when they involve simple algorithms.

      Most of my work involves use of 1D and 2D optimisation algorithms applied to flat glass processing. Very few programmers seem to grasp heuristic algorithms, where there is no exact solution - only an improved solution.

      Attempts to use forums for support on NP-hard solutions can be frustrating. I have been criticised for suggesting a one-line solution for a seeded random number generator, because 100 line solution would be more accurate. The fact that this one-line solution would be 100 times faster, that accuracy is not always critical, and the routine would be called multi-million times is usually ignored.

      I have an excellent book - well thumbed - called "100 Solved Algorithms in Statistics". All written in Basic, but easy to convert. It is rare that a read of that book does not suggest a way forward.

    8. This post has been deleted by a moderator

  2. David Dawson

    I've bounced around several fields of programming, from banking, utilities, small software shops and general consultancy.

    I have never been asked to implement an algorithm of this nature, I asked around my known peeps a bit, and the general agreement was this.

    The only people who will do this are either language library developers or developers on products that require this.

    Everyone else does systems problems. Things like different data consistency models, message ordering/handling lossy data, optimising through put over latency in code or vice versa and differing concurrency models are vastly more important than algorithmic work for the vast majority.

    I was never taught these at uni, and it would've

  3. Frederic Bloggs

    How many professional programmers have a CS degree anyway?

    And does it make any difference at all to the end result? Surely anyone calling themselves a programmer should be able to recognise their limitations and will be able to find and then leverage other people's work.

    Nearly all the work I have done in my professional life (now 40 years) has been anything from straight forward -> really quite hard. Only two have been NP hard. Both of these got solved using good old "monte carlo methods" and using existing libraries (NAG in one case and something that was written for a different, but related problem). Both gave satisfactory answers and in a very short time (as these things go).

    I don't have a CS degree.

    1. Tom Wood

      Re: How many professional programmers have a CS degree anyway?

      " How many professional programmers have a CS degree anyway?

      And does it make any difference at all to the end result?"

      I've worked with and interviewed a number of people who work as software engineers. Some of them have CS degrees, many of them don't.

      There is definitely a correlation between having a CS degree and being a good software engineer. Those that come from other disciplines can make decent software engineers too, but fewer of them seem to. Which is perhaps not that surprising.

      "Surely anyone calling themselves a programmer should be able to recognise their limitations and will be able to find and then leverage other people's work."

      There's a difference between "should be able to" and "can"...

  4. Paul Hovnanian Silver badge

    As a non-CS degreed programmer (Electrical Engineer by training) I had the pleasure to work on and manitain an automatic code generation system some years ago. Requirements documents in (written in technical English), executed code out. The original system was written by a couple of flight controls (Mechanical) engineers. It worked just fine.

    The CS people screamed that the problem was NP-hard, computationally intractable, etc. But we didn't know what any of that meant, so we got it working. It was actually an interpreter, reading the English input and executing commands in real time (no pre-processing required).

  5. Paul Crawford Silver badge

    Yes, I gues.

    I am not a software scientist by training but have ended up programming in C (mostly) to solve difficult problems, not necessarily NP-hard, but not easy for the affordable hardware of the time.

    Most success came from starting with a good book, in particular Numerical Recipes, and timing where things were held up, for example using the profiling tools that come with, for example Visual Studio.

    However, in a number of cases I resorted to approximating the problem or allowing sub-optimum solutions because it was good enough for the system requirements and sometimes vastly faster.

    E.g. I once reduced the processing time of some software that re-projected (warped) an image by implementing my own task-aware cache rather than using the DOS/Windows95 FAT system's own one. Today you don't see file systems that inefficient in common use, and memory is plenty big enough just to load the whole source image in to memory for random access, but original case was ~100MB file in the days when you might have 16MB RAM in a PC.

  6. Def Silver badge

    After 18 years of programming in the games industry (where I've worked on every aspect of game coding at some point or another) and a couple of years in the oil and gas industry (which is just data crunching - mostly), I guess I've dealt with some pretty tricky problems in the past.

    Not sure what the trickiest thing I ever had to work was though. Although they may produce complex behaviour a lot of AI systems tend to be fairly basic finite state machines in design and structure. A lot of the other parts of a game engine are just basic math when all said and done. I guess the hardest part of producing something that runs at 60 frames per second is the optimisation side of things. Trying to fully understand exactly how your data is going to flow (or not as is more often the case) through a processor's caches and trying to design for that seems more like art than science at times.

    Calculating and compressing the routing network for ships sailing between the 80 historical ports of the 17th century Caribbean was a fun problem. From any given port, a ship had to take the most sensible route to any other available port in such a way that shipping routes were automatically created and available for the player to target. The system was written to run offline and produce a binary blob of data that could be reloaded at runtime. The first "working" version took around two days to run iirc - back when 200MHz Pentiums were considered fast. The final version ran in about four hours, I think. I guess today the same code would probably run in a few minutes, and I'm sure I could optimise it a lot better today than I could 15 years ago.

    1. Def Silver badge

      Also, I never went to university. I got fed up with the teachers in school/college asking me whether what had just been written on the blackboard was right or not.

      1. Khaptain Silver badge

        The closest that I got was a similar problem, determing the shortest path between two points. It was only after we had tried, failed, sweated and failed some more that were shown/explained Diijkstras solution to this problem, which at first seems to be so very easy.... Think again

        The problem was given after having received our first examples of recursion..

        Never have I had the fortune/misfortune of being given this kind of "puzzle" within my professional career. I ended up doing "Systems Engineering" related stuff..

        I admit to the fact that I was not mathematically minded, or at least not enough to have ever gone very far down that path.

    2. dogged

      I'd say the the real expertise in programming is identifying the problem in the first place. Most things can be broken down into black boxes and state machines eventually.

      Ironically, I'd say the programmer least likely to reduce his problem to the basics in this way is usually the Maths grad.

      And I am one.

  7. Paddy

    Enthusiastic self-taught programmer rather than a CS major.

    I did Physical Electronics at University not CS, but programming and maths are hobbies and I have coded many CS algorithms and data-structures - Many for the Rosetta Code site: http://rosettacode.org/ - for use at home and at work.

    Every once in a while I am aware that I am solving computationally intractable problems such as selecting the best N of M tests where N ~= 100 and M ~= 25,000 (I used a greedy algorithm: http://paddy3118.blogspot.co.uk/2013/05/greedy-ranking-algorithm-in-python.html)

    Topological sorting is at the heart of arranging VHDL files and libraries for compilation: http://rosettacode.org/wiki/Topological_sort - I've considered implementing my own but the hard part is parsing the VHDL to extract the dependencies rather than the sorting.

    So yes I do solve "algorithmic" and data-structure type problems, but the systems engineering problems are an important part of the whole too.

  8. Pete Spicer

    Disclaimer: I don't have a degree, however I did tackle the fundamentals of this in Decision Maths as part of an A Level in Maths so while I may not be as boffiny as some here, I do understand what NP problems are and the relevance thereof.

    The only time I can actually recall using the various things I learned was in the midst of writing bits for an RTS game, where pathfinding was required. Whether you go down the road of A* or D- or whatever in between, you're still talking dancing about with Dijkstra's algorithm to some degree.

    Having an understanding of the differences between bubble sort, quick sort, exchange sort etc. is always useful too and where it can be an advantage not to use the good old quick sort (if the data is already mostly or completely in order, for example, quick sort may not be any use to you over a bubble sort)

    The other algorithms covered - travelling salesman, shortest method of connecting a weighted graph (like network cabling) have applications out there in the real world but I've never encountered them, and neither have any of the folks I know, but I'm sure there are uses for them.

  9. phil dude
    Boffin

    np hard vs polynomial..

    the comment about graphs is a nice observation. there are some cases of problems that become more tractable, by using "constraints". In the analysis of microarray data this may be gene interactions that don't occur (or are assumed not to). The name for these forms are "cliques".

    As a general rule, physical processes that are time dependent, may not be NP hard, but they are still intractable (see Anton machine).....

    in quantum mechanics the N body problem is another one.

    however, we may still yet discover things from the D-wave machines...

    P.

    1. Don Jefe

      Re: np hard vs polynomial..

      All problems require defining some level of 'constraints', that's true of any problem whether computer based or otherwise. The tricky part is defining those constraints.

  10. Marco van de Voort

    Unlimited scalability

    1) State that NP complete means unlimited scalability.

    2) state that a common engineering rule-of-thumb is that magnitude more precision/scaling costs a magnitude more money.

    3) ask for an upper limit, however crazy.

    4) Let the person asking (who probably just wants to be interesting) prove that with that upper limit to N, the problem warrants thinking (as opposed to copying).

    5) never happens

  11. Anonymous Coward
    Anonymous Coward

    This question makes the mistake of putting all programmers - and programming jobs - in the same bag...

    In other domains the distinction is clear... on one hand you have "scientists" who do the research ... and on the other hand you have "engineers" who take care of the applications.

    Computer science is no different...

    There is a small population of "scientist" programmers (computer scientists) out there that do work on innovative algorithms and "computationally challenging" problems... I think they are a minority and tucked away from their Post Doc research into R&D departments.

    And then there is us - the overwhelming majority of "engineers" programmers...

    I know for example "engineering" programmers who efficiently use complex cryptographic libraries but who - by their own admission - have only a very vague inkling of what goes on inside besides general principles

    and would not recognize an elliptic curve if they met it in the street.

    I also know some "scientist" programmers out there who wrangle with daunting problems like natural language processing but would panic at the idea of writing a small [name your language and environment] application.

    Soooo.... to go back to the original question. Do the immense majority of programmers need to be bludgeoned with theoretical CS and made to fence with computational theory - beyond general principles?

    I don't think so......

    Compare with medicine...what GPs learn is practical operational knowledge that they will need for their practice (yup they're "engineers").... which has very little to do with a what a molecular biologist will need to know to do her research.

    If you're sick would you rather have by your side a GP who has practical clinical knowledge or one who has a lot of theoretical understanding on protein folding mechanisms.... ?

    I'll leave you to see how that applies to IT and "programmers".....

    1. BlueGreen

      this true and much to my regret

      I like hard problems, I don't get enough of them, and they've never been of the computer-science-interesting form. Nearest I get is to de-shag a few hefty sql queries to get them to run in time N rather than N^2. That's about as near as I get to hardcore big-O notation,

      I do feel strongly though that "have only a very vague inkling of what goes on inside besides general principles" is the discriminant between good and mediocre. Someone who actually understands a library/algorithm/cache layout/etc. (or everything all together) is in a very much better position to not cock it up by misapplication (example: getting the 1st, 2nd, 3rd... 30,000th item of a linked list in turn by starting at the beginning of the list each time instead of stepping through it incrementally is the difference between XML DOM x[i] node indexing and x.nextSibling() - wow, instant order of magnitude speedup and don't I look good. If only someone had actually done a little bit of reading instead of calling in a contractor...)

      So sadly in this AC's example I'm the GP you want cos your kid's bashed his arm. I'll never be out of a job. I'm sure I can do so much more though...

      I did go to university and although they gave me amazingly little in terms of real world development skills (which they damn well could & should have) I've no regrets as they've left me with a much larger picture of the whole area with the connections between them - a cartogropher's view from above rather than the dweller slogging upon, and I'm supremely grateful for that.

    2. Anonymous Coward
      Anonymous Coward

      Optional

      http://www.youtube.com/watch?v=2Op3QLzMgSY

      This first SICP lecture sums it up nicely - how algorithms have got lumped in with computing.

    3. Don Jefe

      I believe you're correct and I also believe the lack of definition between the 'scientists' and the 'engineers' is detrimental to not only many businesses, but also to the entire IT sector.

      I'm a physical engineer and within that field there is a massive gulf between the materials scientists and us engineers who use those materials. It is quite rare to see researchers and users working in parallel, it just doesn't work. The boundaries are well defined and no sane person would expect the roles to be interchangeable or combinable.

      In IT, far too many businesses do expect the roles of 'scientist' and 'engineer' to be the interchangeable and the overall results are notably suboptimal. The types of thinking involved are simply too different and although you can force the issue without people dying (usually), neither the scientist nor the engineer are being utilized to their full potential, the sacrifices required to cross too far into the other role ultimately hinder performance.

      Part of this expectation is a lack of understanding by business types. They don't know the differences between computer scientists and computer engineers so they don't hire the right people. Part of it also falls squarely in the IT industry for failing to better define roles within the different groups who practice IT. Obviously part of this is because IT is still a fairly immature industry, but there's a lot to be learned from examining the physical engineering sector. There, the groups and roles are sharply defined and adding the 'correct' people to a project rarely generates any pushback from the customer. IT could greatly benefit from a similar structure both in operational terms and in financial reward for those in the field.

  12. Harry the Bastard

    many years ago, for a project we were doing in a far flung place for her britannic majesty's government, one part required a lot of cabling

    it was not easy to get cable from here to there, transport weight needed to be kept down

    but we knew the cable routes, very many different paths and lengths, and we knew how much cable per reel

    what was the minimum number of reels to do the job?

    in a flash, i thought 'knapsack problem', a bit of cunning coding and hey presto, a cable laying schedule saying which run to do from which reel, the others at the site were most impressed by our efficiency

    triples all round

    1. Anonymous Coward
      Coat

      rookie error surely?

      Wouldn't it have been more fun to code it badly and let it try an exhaustive search of a few trillion options? Shots all round...for seventeen years.

  13. ratfox Silver badge
    Boffin

    I've been asked to find the best way to distribute accounts on forms, considering each account needed to be signed off by a different set of people. I used the greedy algorithm, which was plenty good enough for the sizes involved. But it certainly was not optimal, and the problem is likely NP-hard. Did not bother to prove it though.

    EDIT: it must be the subset cover problem, now that I think of it.

  14. TonyK

    Dots and Boxes

    I once got paid real money to write a Dots and Boxes program (see http://en.wikipedia.org/wiki/Dots_and_Boxes). This game is NP-hard, according to Berlekemp et al's Winning Ways (p.534). But I didn't use any of the sophisticated approximate solutions that have been developed for such problems, I just tried to steer the game to one of the positions that the program could analyse in polynomial time.

    The result was that I was the only human who could beat it on a large board, because I knew how to frustrate its goals.

  15. Warm Braw Silver badge

    Don't forget the data structures

    Algorithms + Data Structures = Programs*

    Not had to tackle an NP-hard problem in the day job, but I have had to work on algortithmic solutions to network routing problems. In one case, the constraint was that the memory was insufficient to hold both the routing graph that the algorithm was currently working on and the route updates that were arriving while the algorithm chugged away. The real challenge was to design data structures that allowed the routing graph to be updated in place while allowing the algorithm to proceed deterministically.

    *Wirth remembering. Sorry. Mine's the one with the Modula 2 book in the pocket.

    1. Frederic Bloggs

      Re: Don't forget the data structures

      * Cough, erm I think you mean Pascal.

      1. Warm Braw Silver badge

        Re: Don't forget the data structures

        > I think you mean Pascal

        Wirth used Pascal for the examples in the book, but went on to develop Modula 2 as a successor programming language.

  16. ausnerd

    Network Routing

    Working in telecom for many years I have encountered requirements to find a shortest path route through a network. I always responded with pointers to literature and proposed that given the hard real-time requirements we compute the best solution in the time allocated. This gives good results without introducing the highly undesirable variation in the time to process requests.

  17. Anonymous Coward
    Anonymous Coward

    I am CS grad and pro programmer. Truth is a barely turned up to any lectures and didn't understand all the mathsy theory stuff at the best of times. Never needed it in the day job. But I still get to look down at you non-grads. :)

    1. Anonymous Coward
      Anonymous Coward

      Too true. I turned up to the lectures and still didn't understand the more maths bits of the theory. Simply avoided games development and anything involving AI. Stick to web development and business systems and the need for doing really hard algorithms goes away most of the time. Some optimisation stuff is necessary, and ensuring things scale properly, but beyond that a good understanding of user interaction and the business processes at hand, plus issues like security etc. is just as, if not more important than remembering famous algorithms.

      1. Anonymous Coward
        Facepalm

        the decline of civilization.

        I always wondered how knowledge got lost in the Dark Ages. I think I just found out.

  18. JeffyPoooh
    Pint

    Real Men use Assembler

    Bubble sorted several thousand items in just a few seconds. Using a 0.9 MHz 6809.

    Yes, I realize it's not "intractable", but with that CPU it might as well have been.

  19. Fehu
    Alien

    24 years Professional Programmer/Analyst/Developer wth they want to call us this year

    I agree with AC_17:53, but I thought Hungry Sean was speaking to the almost universal requirement that every report be presented in the form of a graph, because most management only like to look at pictures, not read words and numbers. Personal side: BS Psychology: started working on an area in CIS but that had a 5 year requirement and after 2 years I was sick of school again, so I just took an AD in Data Processing.

    To reiterate, very little in business level programming is very hard. Lots of programs I've "written" were based on a process that someone in some department set up, but since they really didn't understand programming or databases, it got out of hand. I just normalized their data and translated their process into whatever programming language the platform required. But don't tell anyone I told you this.

  20. InsaneGeek

    Asked to via hardware not code

    While I wasn't asked to code a NP problem, I have a hardware equivalent request. Was asked to find a solution for a system where they wanted to add 50 million new files a day, and compare each file with 2 billion existing files. In short it ended up mathematically to wanting to do something around 3 million random file updates per second. That is something technically I could do with a large chunk of money, but then they told me they wanted to do it over NFS to a shared dataset which I just started to laugh maniacally. I think they got the point as shortly thereafter they rewrote things.

  21. chris lively

    I've been a developer for over 20 years. Words like "NP-Hard" are simply not in my lexicon.

    You just take data, do something to it ( usually ) and send data out. Somewhere along the way someone makes a few bucks. There isn't much hard about it.

    1. Mario Becroft

      Well said chris. I also agree with the other correspondents who have noted that most of the work is routine but occasionally there are hard problems to solve. I would add that it depends on the field, some specialisations are all about solving the hard problems. When I have encountered such problems, I have given them to a specialist. The important thing then is to have a broad understanding so that one can specify the problem, work with the specialist and understand the solution in general terms.

      If one wishes to become highly specialised in solving problems requiring advanced maths, then perhaps one does a maths degree and not a CS degree. Which I would like to do, because it would be much more interesting--but time is ticking by and I just keep doing what pays the bills.

    2. trog-oz

      I agree with chris lively

      I graduated with a computer science degree in 1979 and we never had terms like NP. It all just data and you fiddle with it.

  22. Stephen Channell

    Without NP-hard problems, can it still be called Computer Science?

    I didn't do a Computer Science, but have written several NP-hard components {query path optimisation; query generation; swap solver; expression parser}. If Computer Science undergraduates are not taught how to approach complex intractable problems, how are they going to maintain systems that implement them?

    A few years ago I worked on an Airtime sales/scheduling system where the users needed to pick criteria from across the database to filter slots; and implemented a query generator that would recursively search the meta-model to build a query without chasm or fan traps including all predicates. The review started with "it's impossible", moved to "it's non-deterministic in time" then to "we could use it to build the pre-defined/compiled queries", and went live in the TP system because it was faster than scanning a pre-defined list of all the permutations.

    "NP-hard" is really not a helpful distinction: there are complex requirements and there are simple requirements... if you don't teach students to deal with the most complex requirements you know about; you're not teaching them terribly well

  23. Rol Silver badge

    My current project is to get something useful out of someone else's spreadsheet, "In a jiffy" I replied.

    Oh what a mistake, all of the data has been entered using the most diverse cognitive thinking imaginable and she's adding more by the day.

    I'll give you an example, dates, 12/09/13 good, 12th September 2013, bad, Twelfth of September 2013, worse.

    I set up a mind numbing array of functions to interpret what she had written into proper data and stood back in awe at my talent, then spotted several #VALUE which had come from her spelling mistakes, God was there no end to this.

    Well yes there was, I put validation rules on her spreadsheet which left it like Blackpool lights, with cells everywhere flashing red, then gave it back.

    A simple solution to an intractable problem.

    1. justincormack

      That's NP-annoying not NP-hard.

    2. Frederic Bloggs

      Here's a little job: try name and address deduplication. For about 60 million addresses (for starters). And get them all right.

      That is a real problem, has nothing in particular to do with NP. Probably doesn't even count as "computer science". But it's bloody hard.

  24. david 12

    Simple traveling salesman problem

    One of my first jobs out of school was writing a best-route calculation program. Running on 8088 PC's.

    When I was replaced by a real Computer Science Graduate program, the first thing he told management was that the problem was NP hard, and impossible.

    Actually, there were only 5 nodes, and 4 of those were partial. Computing the optimum route by exhaustive testing took less time than putting the result up on the screen.

  25. Anonymous Coward
    Anonymous Coward

    NP hard problems? All the time!

    Writing algorithms to solve NP-hard problems is my main work. The applications are various planning problems in the automotive industry.

    The important bit when working on NP-hard problems is to stop worrying about optimality. Usually a "good enough" solution is sufficient. You may even find the optimal solution very quickly but would have to spend ages proving optimality. Also, NP-hard problems are often only really hard for a small subset of possible inputs (the "phase transition"), but this will depend on your algorithm.

    Then you should know about the different sorts of techniques (Linear Programming, Constraint Programming, Local Search (Meta-Heuristics), problem-specific heuristics) and when to use which. Not every technique is equally suited to every NP-hard problem. Multi-knapsack? MIP (unless you have dynamic dependencies). JSP/min. makespan? CP works fine. JSP with more complex KPIs? GA.

    Solving these problems does require some understanding of maths, but not an advanced maths degree. This would only be required if you wanted to use LP/MIP exclusively and needed to find effective cuts for your problem. For CP and Meta-Heuristics, a CS degree is much more helpful.

    Alas, in our company of ~100 people (mostly CS degrees), only about 10% have an advanced understanding of how these techniques work, and only four have at some point actually implemented optimization algorithms. Explaining the behaviour of the algorithms to the rest is sometimes hard work. So I would wish that NP-hard problems and techniques to solve them would feature more prominently in CS degrees.

    Working on these problems is tremendous fun and saves me from working on boring "systems engineering problems".

  26. Faye B

    KISS

    As my degree was in Cognitive Science rather than Computer Science, pretty much all we did was study NP hard problems and non-deterministic neural networks. The up side of this is that anything that I can recognise as being deterministic, I know I can solve using basic (or not so basic) algorithms, by breaking the problem down using various problem-solving techniques. It's surprising how many seemingly intractable problems resolve down to using a combination of one or two techniques and a couple of algorithms. The down-side of my degree is that I find very little software in the commercial world to be particularly challenging, just tediously long-winded. I long to work on neural-network designs but so far little has escaped from AI research labs to be used in real-world applications. Even visual processing tends to rely on various mathematical techniques involving massive number crunching. The closest we get is using Hidden Markov Models to fudge the parts where deterministic algorithms fail.

  27. NP-HARD

    Vehicle Routing Problem, Biclustering, Travelling Salesman Problem

    And a few others.

    PhD work is focused upon Biclustering for gene-expression data, with side-orders of Vehicle Scheduling. My MSc project involved solving the hoary old TSP with a variety of algorithms.

    The question of the importance of complexity is really the importance of finding decent metaheuristics which generate decent solutions to intractable problems. Currently, my results show that Quantum Annealing is a promising alternative to Simulated Annealing, and is also very competitive with other population-based approaches such as genetic algorithms.

  28. Anonymous Coward
    Anonymous Coward

    At a previous company I was tasked with implementing a hotel room finder service. The goal was to show availability from a number of providers by querying an integrator's web service that would supposedly provide a generic API for querying any number of providers. I was told categorically that I couldn't cache results, and that the response had to be sub four seconds. The difficulty was that the integrator took typically took between twenty to fifty seconds to respond to any search request. This was on their test system - on their live system the response was even worse. I suggested we remove the integrator (who were absolutely hopeless and had a - I kid you not - six month turnaround for fixes to their core system) and implement our own decent generic API with individual provider integrations beneath it and caching for initial searches. This was shot down by the head of development, who continued to insist on the four second response time despite people like Expedia having a ten to twenty second response time. Turns out her boyfriend owned the integrator, and we were paying them many times more in monthly fees than we ever saw in commission from room sales.

  29. breakfast

    Useful to know about, detail less important

    I can think of a few times in the last 15 years of software development that I have been asked to do something that, when thought through in detail, could be regarded as one of the classic NP-Complete problems like the Knapsack or Travelling Salesman. In most case there was value in recognising them because we could go back to the customer and say "this is tricky, and therefore likely to cost more, are you sure it is what you want?" and suggest some alternative approaches to the problem that would get reasonable results without nearly so much work and they were happy to go for that.

  30. Rob Moss

    Only a couple...

    As a Mathematics graduate I generally find NP-hard problems to be the result of poor planning. I've come across a couple in the past where I had to write some code to take care of them - one to plan the route a set of delivery drivers all starting from the same place would take (basically TSP but with multiple salesmen) and another to calculate the optimal way to load these vehicles, bearing in mind that the stuff that was being delivered last had to go in first, and the stuff that was being delivered first had to go in last. The main problem was time dependency (it takes longer to travel along the M60 during rush hour, for example) but the NP-hardness of the problem wasn't really an issue. All problems are easy to solve given enough resource, and if you need too much resource, you're almost certainly solving the wrong problem.

    1. Don Jefe
      Thumb Up

      Re: Only a couple...

      Absolutely correct! In a functioning, real world scenario, NP-hard problems rarely actually exist. If they do seem to exist it is often because they aren't being examined correctly. I have yet to see more than a handful of non-theoretical scenarios where approaching a problem from a NP-hard perspective was more efficient than reexamining and modifying the situation that leads up to the NP-hard issue.

  31. ThePlanMan

    I don't think I'e ever been asked to solve something NP-Hard that wasn't already 'solved' by just incorporating an external library that will give you the answer you want using the best current techniques.

    However I have definitely been asked to solve algorithmic problems.

    Have worked both in insurance and gambling/financial so they do crop up from time to time.

    This was my favourite, not least because I got to design the solution on paper first, pass it around to my colleagues to verify then implement with great zeal.

    Given two collections of objects containing the same type, one historical and one newer, separate them into three collections, objects that have been removed, objects that have been modified and objects that have been added.

    Solution I came up with has worst case performance of n^2, best case of n and average of 2n.

  32. mlvj

    Two hard things in twenty three years

    In 1990, one of my first roles after leaving university (Mathematics with Computer Science), was to design and implement a set of algorithms to simulate aircraft flying around as part of an air traffic controller trainer.

    This involved going back to the university library, reading up on applied mathematics algorithms, and then implementing some approximation methods. I had about 5 pages of equations which then needed to be implemented.

    The simulator ran on Apple Macintosh machines, and was written in Think Pascal.

    I had about 200 milliseconds in each second to provide the x, y, z, and speed, for 200 aircraft; the rest of time each second was for others to do things like handling the UI and fluffy stuff like that.

    It was a really hard, but really rewarding exercise.

    After that, the next job involving algorithms was in 1999, implementing a set of algorithms to aid the world's largest semiconductor manufacturer plan their supply line - again, a really satisfying job.

    Other than that, in 23 years, that is it!

  33. NomNomNom

    Last place I worked at they wanted me to tie my shoelaces. I told them it was NP-hard but they wouldn't listen. In the end I tied a knot in one shoelace and decommissioned the other.

    I now work in the nuclear industry.

  34. Britt Johnston
    Boffin

    Algorithms are well-behaved

    In our company, most of the complexity comes from the organisation and the users.

  35. Anonymous Coward
    Anonymous Coward

    API and abstractions

    In my experience your average student is not missing out on algorithms and "typical" computer science problems. What they all should have learned is how to design APIs and abstract complexity, something that they will do on a 1000:1 ratio compared to algorithm implementations.

  36. G.Y.

    RL51, the Intel 8051 relocating linker, had to solve the bin-packing problem; solution (first-fit decreasing) was copied straight out of Garey&Johnson; worst-case penalty is 22%, but in practice it worked much better.

POST COMMENT House rules

Not a member of The Register? Create a new account here.

  • Enter your comment

  • Add an icon

Anonymous cowards cannot choose their icon

Biting the hand that feeds IT © 1998–2020