Meanwhile in CACM, Moshe Vardi writes Lost in Math?

TCS is surely blessed with mathematical beauty. As a graduate student a long time ago, it was mathematical beauty that attracted me to TCS, and continued to lead my research for many years. I find computational complexity theory (or complexity theory, for short), with its theorems (for example, the time-hierarchy and space-hierarchy theorems) and its open questions (for example, P vs NP), to be hauntingly beautiful. Beauty, yes; but what about truth?Here here on the beauty of complexity. So what about truth? I cover much of this in my P v NP survey. In short the P v NP captures the most critical aspects of what is efficiently computable but it is not the endpoint. Nevertheless P v NP captures both truth and beauty and that's why the problem has so captivated and guided me throughout my research career.

## No comments:

## Post a Comment