Publication Details
Title: Program Correctness Checking and the Design of Programs That Check Their Work
Author: M. Blum and S. Kannan
Group: ICSI Technical Reports
Date: December 1988
PDF: http://www.icsi.berkeley.edu/pubs/techreports/tr-88-013.pdf
Overview:
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.
Bibliographic Information:
ICSI Technical Report TR-88-013
Bibliographic Reference:
M. Blum and S. Kannan. Program Correctness Checking and the Design of Programs That Check Their Work. ICSI Technical Report TR-88-013, December 1988
Author: M. Blum and S. Kannan
Group: ICSI Technical Reports
Date: December 1988
PDF: http://www.icsi.berkeley.edu/pubs/techreports/tr-88-013.pdf
Overview:
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.
Bibliographic Information:
ICSI Technical Report TR-88-013
Bibliographic Reference:
M. Blum and S. Kannan. Program Correctness Checking and the Design of Programs That Check Their Work. ICSI Technical Report TR-88-013, December 1988