Complexity Theory

Next reading meeting will touch on theoretical computer science. We will be seeing how computational complexity can potentially offer new insights into philosophy of mathematics. We will be reading Scott Aaronson’s survey paper Why Philosophers Should Care about Computational Complexity.

For the meeting, we expect attendants to read in advance sections 1-5, 8-9 and 12 of the paper, available here.

The meeting will have a presentation by Andrea and Noel, followed, as usual, by a discussion.

The P vs. NP problem, one of the seven Millenium Problems, is one of the most relevant unsolved question in theoretical computer science. The progress in the last decade, however, has been little. Can information theory and philosophy of information provide new insights as to why these classes should be distinct (or the same)? Pieter Adriaans will be offering a talk on the subject, followed by a discussion.

‘In this talk, I will present a perspective on the P vs. NP problem in the context of philosophy of information. P is the class of decision problems that can be solved in time polynomial to the length of their input by a deterministic computer. NP is the class of problems that can be solved in polynomial time by a non-deterministic computer. This description gives a direct relation with the philosophical question of determinism versus non-determinism and the problem of the interaction between information and computation. This suggests that a careful analysis of the flow of information through computational processes might help us to understand the P vs. NP problem better. Unfortunately, the existing theories of information are not very adequate for this purpose. Shannon information is based on a statistical notion of entropy that is not directly applicable. Kolmogorov complexity defines a structural concept of entropy that is asymptotic and not computable. Apart from that the classes of problems known to be in NP do not have a structure that easily facilitates the application of information theory. There is, for example, no univocal theory of information measurement for finite sets of numbers. This complicates an information theoretical analysis of the subset sum problem and related problems in NP considerably. I therefore propose to look at a new class of problems that I call Multiple Mutual Key (MMK) decision problems. The case for MMK not being in P is at least prima facie stronger than for other problems in NP since the checking function is a repeated application of one time pad code ciphers, which is a provably safe encryption technique. Apart from that problems in MMK are constraint free: any binary string of an adequate length defines an MMK decision problem. This implies that the average case complexity is high and makes it easy to apply maximum entropy techniques.’