Complexity

A means of understanding how systems work and interact with our world, and ultimately what can be solved or not solved by machine learning systems.  Technical.

Chasing Complexity

MIT News  Larry Hardesty

Massachusetts Institute of Technology faculty member Ryan Williams in the Computer Science and Artificial Intelligence Laboratory has made a key contribution toward solving the problem of P versus NP. Much of that contribution stems from his attempts as an IBM research fellow to bridge a divide within theoretical computer science, between researchers who work on computational complexity and those who design algorithms. Williams considered exploiting the symmetry between these two camps, as establishing an algorithm's minimum running time requires generalizing nearly all possible instances of a specific problem that it will ever have to face. His focus was on adapting algorithmic design methods to establish lower bounds. Williams first proved the hypothetical link between algorithms and lower bounds, and then demonstrated its application to a very particular class of logic circuits. "This is essentially the circuit class where progress on P not equal to NP stopped in the mid-'80s," Williams notes.  .... "