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 |