On the complexity of the correctness problem for non-zeroness test instruction sequences
arXiv:1805.05845 · doi:10.1016/j.tcs.2019.03.040
Abstract
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 programs of a very simple form, namely instruction sequences, and a very simple problem, namely the non-zeroness test on natural numbers. The instruction sequences concerned are of a kind by which, for each , each function from to can be computed. The established results include the time complexities of the problem of determining whether an arbitrary instruction sequence correctly implements the restriction to of the function from to that models the non-zeroness test function, for , under several restrictions on the arbitrary instruction sequence.
arXiv comment32 pages, minor revision with several obscurities made clear
References in corpus (5)
- On algorithmic equivalence of instruction sequences for computing bit string functions
- Instruction sequence based non-uniform complexity classes
- On instruction sets for Boolean registers in program algebra
- Instruction sequence size complexity of parity
- Axioms for behavioural congruence of single-pass instruction sequences