Name
Title | ||
|---|---|---|
On the complexity of the correctness problem for non-zeroness test instruction sequences. |
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 n>0, each function from {0,1}n to {0,1} 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 {0,1}n of the function from {0,1}⁎ to {0,1} that models the non-zeroness test function, for n>0, under several restrictions on the arbitrary instruction sequence. |
Year | DOI | Venue |
|---|---|---|
2018 | 10.1016/j.tcs.2019.03.040 | Theoretical Computer Science |
Keywords | Field | DocType |
Non-zeroness test,Instruction sequence,Correctness problem,Computational complexity | Discrete mathematics,Natural number,Instruction sequence,Test functions for optimization,Correctness,Mathematics | Journal |
Volume | ISSN | Citations |
802 | 0304-3975 | 1 |
PageRank | References | Authors |
0.38 | 5 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jan A. Bergstra | 1 | 1946 | 240.42 |
| Cornelis A. Middelburg | 2 | 487 | 49.21 |