Further to the Lego tool I mentioned last night: I had coffee with Jamie this morning who introduced me to the term ‘intractable problem’ in the context of computational complexity theory. Reading up a little on it has led me to conclude that dismantling Lego is NP-complete.
Although any given solution to an NP-complete problem can be verified quickly (in polynomial time), there is no known efficient way to locate a solution in the first place; indeed, the most notable characteristic of NP-complete problems is that no fast solution to them is known. That is, the time required to solve the problem using any currently known algorithm increases very quickly as the size of the problem grows. As a consequence, determining whether or not it is possible to solve these problems quickly, called the P versus NP problem, is one of the principal unsolved problems in computer science today.
Maybe I’m pushing the simile too far, but it’s fun to think about Lego from a different angle. Also, Jamie introduced me to his old Lego disassembling method of throwing it against a wall. I think I’ll hold that one back from my kids.
Documenteering 