Walter Dean

The project bridges philosophy of mathematics and the study of algorithms and complexity in theoretical computer science.  It concerns the significance of barriers -- i.e. mathematical results illustrating why certain problems currently believed to be "hard" cannot be resolved using existing proof techniques. Illustrative of such problems is the famous P vs NP question which asks whether the task of finding a solution to a certain kind of finite problem is intrinsically harder than that of verifying that a given solution is correct. A solution would have substantial ramifications -- e.g. for data security, quantum computation, and artificial intelligence. But after it was originally posed in 1971, P vs NP remains unsolved and is regarded as among the most difficult open problems in mathematics.

The discovery of barriers helps to explain this by illustrating how successive strategies for resolving P vs NP have failed. A central thesis of the project is that barriers illuminate not only technical impediments but also more general limitations of human knowledge both inside and outside mathematics. This theme will be explored in the context of sub-projects exploring the methodology of barriers as a case study in mathematical problem solving, the history of multiplication algorithms in the frame of the question "is it intrinsically more difficult to multiply than to add?" and complexity-theoretic limitations on the use of artificial intelligence for mathematical proof search.