2nd Semester 2021/22: Philosophy of information and the P vs NP problem
- Pieter Adriaans, Daan van den Berg
Philosophy of Information deals with the philosophical analysis of the notion of information both from a historical and a systematic perspective. In this course we will investigate the well-known P vs. NP problem from an informational perspective. A basic insight is that the interaction between information and computation is still ill-understood. We’ll investigate information aspects of deterministic and non-deterministic processes and analyze the possibilities of developing a more refined theory of information measurement (differential information theory) that allows us to follow the ‘flow’ of information during computational processes. This analysis gives us a taxonomy of problems in NP that creates new perspectives on the phase transitions in the underlying domains. The theoretical work is corroborated with a growing body of empirical results and suggests many new domains for experimental work. The course therefore offers perspectives for both students that have a more theoretical interest as well as students that like do some programming on real life problems.
Three weeks of interactive classes, ca. 6 to 8 meetings. One or two evaluation meetings to discuss individual projects/essays. The exact schedule is to be determined.
Elementary understanding of mathematics, logic and information theory (Shannon, Kolmogorov).
- Homework assignments, presentation, small report.
P.W. Adriaans, DIfferential information theory (https://arxiv.org/abs/2111.04335) i
P.W.Adriaans, Information, Stanford Encyclopedia of Philosophy (https://plato.stanford.edu/entries/information/)
Subset Sum & the Distribution of Information"(Van den Berg & Adriaans 2021) (https://www.scitepress.org/Papers/2021/106732/106732.pdf)
Course will be held via Zoom. I will not be in Holland during the course so all contacts will be on line.