Computational lower bounds using diagonalization |
| |
| Authors: | M V Panduranga Rao |
| |
| Institution: | (1) Indian Statistical Institute, New Delhi, 110 016, India |
| |
| Abstract: | What can a computer with limited resources like time and space accomplish? Can it solve our favourite computational problem? These are the kind of questions that we implicitly ask when designing ‘efficient algorithms’. It is also interesting to know which problems cannot be solved with computers operating with limited resources, no matter how smart we are as algorithm designers. Moreover, given a problem, we would like to know the lower bound on such resources required to solve it using a given computer. This article in two parts, discusses an important technique called diagonalization for establishing such lower bounds. In this part we will fix a model of a computer —indeed, one that is as powerful as any other known mechanical model — and explore some important features of this model. In the second part, we will introduce diagonlization, its applications and potential shortcomings. |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
