On the complexity of the correctness problem for non-zeroness test instruction sequences

J. A. Bergstra, C. A. Middelburg

This paper concerns the question to what extent it can be efficiently determined whether an arbitrary program correctly solves a given problem. This question is investigated with p…