I want to post about things that I am reading as a record and a way to point out interesting resources on this blog. With that in mind, I read a really awesome paper the other day about philosophy and computational complexity theory.
The paper is called [Why Philosophers Should Care about Computational Complexity](Why Philosophers Should Care about Computational Complexity). It is a really fascinating paper covering a variety of applications of computational complexity to philosophy, asking for more communication between these fields.
I found it interesting to see how arguments about complexity could resolve more deeply into problems that are otherwise considered by the more course computability argument. In other words, the limits of complexity, such as the need for 'effectively computable' solutions allows us to see a little deeper into some problems that otherwise seem quite difficult, and often in very clever ways.
I won't try to reproduce any of the arguments- I suggest just reading the paper, or at least the introduction, to see if you are interested.
Some noteable parts are complexity and evolution, PAC (I read Leslie Valiant's book Probably Approxmiately Correct, which is also great), and the discussion of what is knowable and what does "knowing" mean. The other theme that I think is interesting is the relationship between computation and physics, such as in the computing power of the physical world and the limits of the physical universe in its ability to perform certain computations.