Monday, April 25, 2011

The dance of politics, faith, and EXPTIME problems

It's been a while since I last posted, cause I've been keeping busy in other things. Now that I have a deadline coming up, my natural inclinations to shirk work are rising again. This post begins with a rather frightening thing I've noticed about news coverage in USA and the amount of debating that goes on about lots of issues. It seems like everyone has an opinion about everything, and are hardly interested in any other points of view. Though I don't claim to know the subtleties of any of these issues, the lack of interest in an actual debate annoys me no end, even though I can see the reasoning and vested interests in avoiding actual debate.

Finding correct answers to anything but the most trivial questions is a hard problem. I can give a quite few reasons for this, causality, complexity of the problem (watch my new TV favorite NUMBERS for a very hand-wavy explanation of what I mean here :) ). Tracing things back to computer science, my bread and butter, "hard" problems are usually considered in a class of NP problems. These are problems to which solutions cannot be computed by any known method in time proportional to a polynomial function of the input size. In layman's terms, this is a class of problems to which computing an answer is hard, using regular computers in any sane amount of time. This is why your online transactions are safe, cause you can't factor numbers into their prime factors easily. But the interesting part in this class is that the solution can be verified in polynomial time, i.e. easily. For example, if you know a possible factorization of a number, say 20 as 2x2x5, you can check it simply by multiplying them. Now CS has only reached these problems till now.

Coming back to political debates and arguments, you'll see that even though you may find a solution by some definition, actually proving it to be a correct solution is not possible easily. In fact whether a solution exists is not know apriori. To me at least, and for life as it is, these problems are much more interesting. After a little searching, I found out that these problems are called EXPTIME algorithms. Obviously, this claim of mine is not exactly true, but what I'm trying to say is that solutions to these problems can be found and verified in exponential time, a.k.a. very long time in layman terms, but still possible. For the time being lets assume my definition of this class of problems is accurately represented by EXPTIME, but it's more likely the EXPSPACE class (look at the wiki pages for these if you're interested). My point is simply that these are the most encompassing of all problem classes I could find.

Now, even with NP problems, algorithms only attempt to produce an approximately correct solution, since an exact algorithm can only be computed once P=NP is proven. Till then, the only known algorithm for these is pure brute force. This can be understood by trying to get out of a maze by going through every possible path. Since, in reality there are means of finding out if you're going horribly wrong (like towards a waiting minotaur), you can prune your search "tree", which is the basis of most AI methods like the ones used by Chess playing computers like Deep Blue. The thing is that for finding solutions to generalized problems, knowing when a solution is correct is really hard too, so we must rely on some intuition or develop some approximation to model the problem. The real world analogue to this is faith, i.e. when something is so complex that understanding it goes beyond one's limit of knowledge, one starts to make assumptions and trust the assertions made by someone. The gap in science and religion stems from this very fact, since science keeps encroaching on religion and magic. I quite liked the explanation given in a trailer to the upcoming Thor movie, which said that his world was one where science and magic merged, as everything could be proven by science, so everything was magical yet scientific. Coming back, faith is a sanity check employed by most problem solving machines in nature, due to the inability of any mind to model anything in its entirety.

For the CS inclined and otherwise, it's important to look at this in terms of a tree. Any brute force search is visualized as going from the root of a tree to a specific leaf which is our correct answer. We must choose a branch at every decision making step. Faith is like turning a blind eye to certain branches, saying those are off limits and our desired leaf can't possibly be on one of them. The scientific method, and to an extent an actual debate, is quite the opposite, it must traverse every possible branch unless proven to be wrong. A lot of this also works from a bottom-up philosophy, by saying we want to reach this leaf, so lets make assumptions along the way down to the root to get us here. The alternate is a top-down approach, where you want to find the leaf by traversing branches. While faith will claim assumptions as it assumes the leaf to be paramount, logic tries to find the "right" leaf by finding reasons to choose each branch to be correct.

If any of that made any sense to you, it's easy to see that faith and logic can rarely agree. Thus it is so very important to understand why we're trusting something or someone. Blind faith is like going through a maze with a blindfold on, you may think you can get out with your amazing senses, but it's likely you'll hit the minotaur, and your glorious life will come to an abrupt end. Even so, a large populace will never adopt a purely logical approach because certain effects cannot be modeled by pure logic, without using probability and statistics, which as we all know, everyone hates cause you can use them to prove pretty much anything. True nirvana can only be attained by realizing that there is no "correct", there's only entropy maximization. So unless you want to expend a lot of effort to fight randomness, the only option is to mostly accept things that don't make sense, and fight your small battles against it, hoping that like a butterfly flapping its wings, your feeble pokes at randomness can actually curtail and guide it.