Archive for January, 2012

On Problem Complexity and Artificial Constraints

January 2, 2012 1 comment

Recently a colleague, a fellow CS professor, asked for my expert assistance in moving a sofa from the basement to one of the rooms of his house. The sofa was not heavy, but too bulky to be carried by one person. The whole procedure was expected to take no more than 15 minutes. We easily transported the sofa from the basement to the entrance of the destination room, and then we encountered an unexpected obstacle. The sofa was too wide to get through the room’s entrance.

We put the sofa down and quickly came up with a solution. The sofa is to be taken outside the house and be carried to the porch adjacent to the destination room; then the sofa is to be lifted to the porch’s railings, picked from the other side, ¬†and be carried to the room. The room’s entrance from the porch was wider than the one from inside the house. The only problem was that lifting the sofa to the porch’s railings and then picking it up from the other side required two more people. I told my colleague that I’d be available for the rest of the day, and let him solve the personell problem of finding two additional persons to realize our solution.

In a couple of hours, my colleague informed me that he had found two additional people for the task, who could be at his house in an hour. I told him that I’d be there. I asked him who were the other two people he’s recruited. It turned out that my colleague had friends and collaborators in other departments, and these two served on the faculty of Industrial Engineering and Architecture, respectively. How many academics does it take to move a sofa?

When I arrived to the house, my colleague informed me that the professor of Industrial Engineering was going to be a couple of minutes late. The professor of Architecture arrived soon thereafter and immediately inquired about the nature of the moving job. Then the conversation proceeded as follows:

-Can I have a measuring tape, please?

-Yes, you can, but I have measured the entrance and it is narrower than the sofa.

-Can I have a measuring tape anyway?

-Here you go.

-Can I have a screwdriver, please?

Then, in no time, the Architecture professor removed the destination room’s door from its hinges.

-Can you give me a hand carrying this thing?

A couple of minutes later the sofa was in its intended destination and the door was back in its original place. I was completely dumbfounded. “But how did you know that the door could be removed and placed back so easily?” “Come on, give some credit; I know these things inside out. With these kinds of doors it is easy.” Then the professor of Architecture remarked something about the house’s lighting needing adjustment and bid farewell. The arriving professor of Industrial Engineering was informed that due to an unexpected optimization of our moving algorithm, the job was already completed by involving only two persons.

I could not stop thinking about this incident. We had a problem that required four persons to solve. Furthermore, these four persons were expected to carry a sofa around the house and raise it to the railings. And then the same problem was solved with only two people, who did not even have to perform that much work. Thus, the second solution was more than twice as efficient: it required half as many persons who had to perform less work. All of this is because an artificial constraint was removed—the door was temporarily removed from its hinges making the necessary space for the sofa.

I could not help but think how often we experience similar kinds of situations in software research. I’ve seen instances when researchers are working for years on fully-automated solutions to important problems. Fully-automated solutions are notoriously hard because they have to ensure absolute correctness and safety. However, if a human user can provide some input, the problem suddenly becomes manageable and can be solved in a reasonable amount of time. In other words, semi-automated solutions are as valuable but also tractable.

How often do we impose artificial constraints on the problems we want to solve? How often do we think that the proverbial door would be too difficult to temporarily remove from its hinges? Do we perhaps unnecessarily complexify the solutions we propose to improve our chances of getting funding or publications? Well, one thing for sure–helping your colleagues move furniture can give you new insights on your research!

Categories: Uncategorized