Optimization Craft

# Solving NP-Complete Problems for a Living

I have the best job in all of computer science:  I solve NP-Complete problems.  “But”, I hear you say, “NP-Complete means ‘can’t be solved’”.  Yes.  That’s what makes it so fun.

I build the software used to create integrated circuits.  This is a field thick with NP-Complete problems.  Determine where to place the components on a slab of silicon to minimize interconnect delay:  NP-Complete.  Determine which of the millions of components use high-power logic (fast but battery draining) versus more battery-friendly low-power logic.  Pick a route for all the wires that hook up the components:  NP-Complete.  And, the granddaddy of all NP-complete problems:  Does there exist an input where the Boolean logic network gets the wrong answer (satisfiability).  I could go on.

I work in a multi-billion dollar industry (called Electronic Design Automation, or EDA), charged with solving the world’s toughest software problems.  The success of every electronic device from cell phones to network switches to computers, hinges on EDA.

How do I do it?  A bear charges a pair of campers.  The first camper starts to put on his running shoes.  “You can’t outrun a bear,” observes the second camper.  The first camper replies, “I don’t have to outrun the bear.  I have to outrun you.”

I don’t have to solve these NP-Complete problems.  I have to outrun everyone else trying to solve to these problems.  That means compared to anyone else’s software, mine must generate integrated circuits that are faster, have longer battery life, have fewer bugs, and are easier to manufacture.  Because we can’t reach the optimum, the race never ends.

My company, Synopsys, is racing ahead.  For example, most of the electronics that brings you this message were created with Synopsys software.  But, the competition is fierce and integrated circuits evolve quickly.  There is always a drive to do better.  That brings me to why I’m writing this.  I need help.  I need smart and creative engineers to make the next generation of EDA software.  This kind of software is not for the casual programmer.  Getting to the optimum is impossible, but getting closer than anyone else is matter of superior intelligence, creativity and raw software skill.  Interested?

Share and Enjoy: