2nd Semester 2021/22: Philosophy of information and the P vs NP problem

Instructors

Pieter Adriaans, Daan van den Berg

ECTS

6

Description

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.

Organisation

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. 

Prerequisites

Elementary understanding of mathematics, logic and information theory (Shannon, Kolmogorov).  

Assessment

Homework assignments, presentation, small report.

References

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)

(https://youtu.be/tlt2y_6pkyw)