Monday, December 22, 2014

Why Math?

When I was teaching math and computers in college, some freshman would invariably ask: why do I have to learn this? Why math? One of my professors replied: "Why art? Why a baby?"
He was right. In its purist form, math is art. Anyone who has looked at fractals can tell you that. Zoom in on a Mandelbrot set and you'll find another one underneath. I'm sure the movie Frozen wouldn't have been the same without them.
http://en.wikipedia.org/wiki/Julia_set
Pythagoras, the discoverer of the formula for a triangle's hypotenuse and prime numbers, was considered a philosopher by the ancient Greeks. This is the realm of number theory, where you get to peek at the secret rules of the universe, but there is rarely any progress. It's still intoxicating to play with, though, because you find patterns. If you take two to a prime number and subtract one, that number will also be prime. There are numbers (like 6) Pythagoras called "Perfect" because when you add up all their factors, it makes the number itself. Some pairs of numbers form each other.
Pure math is concerned with topics like how do I find this animal, or how can I prove this general rule I came up with? Sadly, mathematicians spend so much time locked up with this ideal of beauty that they sometimes refer to short, elegant proofs as "sexy."

The moment math applies to the real world, it's soiled and most purists won't touch it anymore. For example, guys like Diffie and Hellman noticed that certain math problems easy to describe and generate but incredibly difficult to reverse to the solution. Such one-way behavior is ideal for cryptography. Their discovery forms the basis for your secure computer transactions when you type https. Applied math people ask questions related to the real world, like "how can I fly to every city on my route the cheapest way possible, visiting each exactly once?", which is known as the Traveling Salesman Problem. If there are ten cities, there are 10 choices for the first stop, 9 for the second, and so on. Before you know it, the number of combinations explodes into 3,628,800 routes. This unruly behavior is known as a Non-Polynomial equation (NP), and it appears in every aspect of life, from trash collection routes to odds in Poker or the best move in Chess. It's a very dangerous animal.

Polynomial equations (P), by contrast, are simple and tame. Problems such as sorting this list of students by score, or finding the amount of light on every surface in your computer simulation are based on the number of data points squared or cubed at worst. Engineers can find cheats to reduce the complexity to N log N or 6 N squared. Throw enough computing power at P problems and they go away. Most of computer science revolves around the proper understanding of and taming of combinatorics. Knuth wrote the definitive series of textbooks on this topic. http://en.wikipedia.org/wiki/The_Art_of_Computer_Programming 

https://www.youtube.com/watch?v=SC5CX8drAtU
Why is NP so dangerous? Some NP problems have a flaw if you look at them the right way. You don't need to solve the perfect abstract problem, only the common case. For example, the costs to fly somewhere in the Traveling Salesman problem are primarily due to fuel costs and hours or crew time, both of which are dominated by the absolute distance between two points. For most cases, if you put a dot on each city on the map, a four-year-old could play connect the dots along the outer rim and get a solution that's close. These heuristics (greedy algorithm) are not a guarantee of the best solution, but are usually within an acceptable percent of perfect in almost no time. The Maps program on my wife's phone helped us find the best route to visit every quilt store in Minnesota.

In my job as an engineer, each time I could get "close enough" to an NP problem like the Knapsack Problem for scheduling computer resources, it was worth a patent. Each time I "knew" it could be simplified, it took me two months locked in solitary for a prototype and a year to build a safe version for the customer. They are deceptively simple, with the promise of big payoffs.

Numb3rs (2005) PosterThe problem comes when you can't find a hack. Mathematicians put these hard problems in a zoo and name them. They fill journals and books. To get into this hall of shame, they need be mapped with a few word changes and order P math steps into another NP complete problem. Thus, if you can solve ONE of these monsters in P time, all of them will fall to the same sword. In the TV series Numbers, the main character nearly has a breakdown when he spends a year trying to crack this problem. I can see how easy this would be, fixating on something that is just beyond your grasp and having faith that it just takes the right point of view and tenets. Math is still part philosophy. Through the use of neural nets we can model an NP problem with circuits and allow the current to settle to its natural solution state. In quantum computing, it should be possible to just "guess" the right answer. The computer will see all solutions simultaneously and collapse the waveform to the one we want. All of this could happen within our lifetime, and it will transform the economy and touch every science. "Give me a lever long enough and a place to stand and I can move the world." -- Archimedes, another dead Greek geek.

Why do I care? In 2008, I lost six months of spare time and sleep trying to conquer a simple puzzle called Eternity 2--a simple 256 piece puzzle so devious that to exhaust every possibility on existing computers would probably take until the sun burns out. But what if it has a weakness or I could get close enough? The solution was worth a couple million dollars, and would prove P=NP. I solved other puzzles to earn the placement of 4 of the pieces, but this didn't make the puzzle any easier. With the initial set of corner pieces and random guesses, I notices that in 200 attempts, one of the choices for upper-right corner went further than all the others. My working theory was that of fixed-point iteration or seeking the path of least resistance through repetition--like Newton's square-root technique or the Hailstone Seed Problem, the problem wanted to converge on a solution and would lead me to that end. Therefore, I would test each of the options for an added piece a few hundred times and measure successes. I only chose those additions with overwhelming success, or split the search when there were two close options. Most attempts with some wouldn't get past the halfway point. Indeed, some choices might make the problem unsolvable. By following success, I hoped to find increasingly better solutions.  I came closest with 211 sequential pieces and 22 edge mismatches in the overall attempt. I also suspect that the pieces with multiple triangle of the same color were a flaw to exploit. I stopped when I reached 19 edge mismatches and forced myself to quit cold turkey.

IQ is nothing without common sense. Here's the problem, like a lottery, I could EARN a million dollars in the time it took me to solve this one puzzle, with no general purpose solution. I also wanted to spend time with my children and wife. (I have a more normal definition of "sexy".) Though the siren song of NP calls from time to time, I spend my spare cycles writing fiction now, making other art that will hopefully last beyond me or improve the world today. That is how this discussion began after all. Math practiced properly is a life-changing philosophy.