The powerful imperfection

Imagine packing for holidays. You have a fixed amount of space in the car and a variety of irregular shapes (suitcases, coolers, a guitar, tennis rackets, two dogs, a bag of snacks, …).

• The Struggle: You want to fit everything in without leaving anything behind.
• The Complexity: There is no simple formula to tell you the perfect orientation for every single item.
• The solution: Approximation

Humans can easily solve this problem because we use a heuristic approach (a mental shortcut), like “put the big heavy boxes in first and stuff the pillows in the gaps.” Our solution is approximate. It is not perfect or optimal, but it gets stuff done.

A classic compute machine cannot easily solve this issue because it goes for the optimal solution. Starting with packing one object, then adding others, the combinatoric work to figure out the perfect situation increases. Adding just one more item can double, triple, or quadruple the work. Very quickly, the number of possibilities exceeds the number of atoms in the known universe. It’s called the combinatorial explosion.

To solve Non-Deterministic Polynomial time complete (NP-Complete) issues like this, machines use decision-trees. For every choice (How do I orientate the running shoe in the car ?), the tree branches off. The tree will grow incredibly wide very quickly because the items interact with each other (the running shoe’s position affects where the pillow can go), we often can’t know if a choice is bad until we’ve followed it all the way to the very bottom of the tree.

To stay sane, humans solve the issue by “cheating”. We use heuristics and approximation. General rules which guarantee not a perfect solution, but a good-enough answer. Computers nowadays do the same trade-off: Optimal vs. Time.

98% perfect in 2 seconds is much better than 100% perfect in a million years.

In modern AI, NP-Complete problems are the invisible “walls” that define what an AI can and cannot do efficiently. While we often think of AI as having infinite processing power, it is actually a constant battle against the complexity of the Combinatorial Explosion. We can see this work in the following domains:

In these areas the NP-Complete problem still exists because their solution needs the truth as the optimised solution, not an approximation. It is where Quantum Computing and qubits can explore new paths and possibly break down some of these complexity barriers, but that is a different story.

Other AI systems, seem to be more and more successful in solving many of the NP-Complete issues because it found ways to ignore the need for perfection in exchange for the ability to get an answer before the end of time. We accept the 2% error rate, look at how you most likely use ChatBots or agents. Not always perfect but they get things done and bring the answers we can live with. It does this by attention approximations, token weights and other highly mathematical relaxation tricks.

In a way, by transitioning from “Old AI” (which always tried to figure out things perfectly), to “Modern AI” (which uses heuristics to make a good enough guess), some of our systems of today have become more efficient by becoming creative, error-prone and intuitive. In doing so, they’ve become a little bit more human. Or have they?