Today I bounced some ideas off Henri and it made me realize that I have, for a very long time, slightly misunderstood a fundamental problem in Computer Science.  In particular, the CNF-SAT problem is arguably at the core of computation complexity, which is one of the cores of Theoretical Computer Science.  The solutions I have seen have mostly been expressed as a function of n, the number of variables.  Today I learned that this is not a good measure, at least not the best measure, of the quality of the solution.  Moreover, I have realized that technically all such measures must be given as a function of the size of the input, especially if some inputs can be exponentially longer than others.

This all sounds very gobbly-gook, but in simple terms, I have realized that something I have thought about in a particular way for a very long time, is — in reality — different from what I have imagined.  I guess the lesson is to constantly be on the guard for faulty assumptions.  In this case the effect on my life up to this point is small, but it is not impossible that is has a larger impact on my future.  I hope to soon (within the next six months) write a paper about SAT, and it is a good thing that I learned about this fact now.  If I had worked with SAT problems for a long time, I might have known this, I suppose.

It makes me wonder about other things on the periphery of my knowledge that I might harbour misconceptions about.  The more peripheral, the more amusing these debunked myths are (although I expect not many will find my newly-acquired insight about CNF-SAT amusing).  The closer they hit home, the more serious and dramatic the impact.  But somewhere in between is a class of “facts” that play a not insignificant role in the way we view the world.  If these assumptions are invalid, we (I) may have to reevaluate other assumptions.  I was going to cite a brilliant and meaningful example, but I couldn’t think of one.