Program Correctness Checking and the Design of Programs That Check Their Work
| Title | Program Correctness Checking and the Design of Programs That Check Their Work |
| Publication Type | Technical Report |
| Year of Publication | 1988 |
| Authors | Blum, M. E., & Kannan S. |
| Other Numbers | 499 |
| Abstract | A program correctness checker is an algorithm for checking the output of a computation. This paper defines the concept of a program checker. It designs program checkers for a few specific and carefully chosen problems in the class P of problems solvable in polynomial time. It also applies methods of modern cryptography, especially the idea of a probabilistic interactive proof, to the design of program checkers for group theoretic computations. Finally it characterizes the problems that can be checked. |
| URL | http://www.icsi.berkeley.edu/pubs/techreports/tr-88-013.pdf |
| Bibliographic Notes | ICSI Technical Report TR-88-013 |
| Abbreviated Authors | M. Blum and S. Kannan |
| ICSI Publication Type | Technical Report |