/ artificial intelligence

Notes on Computational Complexity

I didn't really have a topic prepared today, so I'm just going to jot some notes instead of writing anything grandiose. I've been focusing on code and fiction these past few weeks and not theory. But I said every other Thursday, and habit building is hard.

I've been reading, (though only the vaguely preliminary skim) about Computational Complexity as it relates to philosophy[1] and an Information Theory of Consciousness [2]. I'm just going to post an outline of the problem of Computational Complexity's relationship with philosophy.

The idea that I'm finding interesting is that for most philosophers[3] what is important is 'how' solve a problem, or even 'why' we solve a problem, and once we get passed the hurdle of knowing that a problem can be solved the rest of the issue is best left to the engineers. Rarely is it taken into account that there are some interesting disconnects between what is theoretically possible and what is actually possible.

Much of the trouble in computational complexity comes with solving what we call NP-complete problems, that is to say, a non-deterministic Turing machine can solve the problem in polynomial time, or, more clearly perhaps, these are the types of problems we currently cannot solve in any efficient measure of time using current technologies. Solving NP-Completeness is something of a holy grail in theoretical computer science.

In this way, even if a problem actually can be solved algorithmically it would take an astronomical amount of time to actually solve said problem. Does this count, then, as a hurdle we have overcome? Philosophically, we may say yes, but practically it may make more sense to say no.

Sorry this post isn't longer, I really did just want to introduce the concept for later posts as I have an assignment to finish for tonight. Also, note to self, I need a better footnotes plugin.


  1. http://eccc.hpi-web.de/report/2011/108/ ↩︎

  2. http://www.biomedcentral.com/1471-2202/5/42/ ↩︎

  3. At least among the ones I've met ↩︎