Back to Search
Start Over
On the complexity of the correctness problem for non-zeroness test instruction sequences
- Source :
- Theoretical Computer Science, 802, 1-18. Elsevier
- Publication Year :
- 2020
- Publisher :
- Elsevier BV, 2020.
-
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.<br />32 pages, minor revision with several obscurities made clear
- Subjects :
- FOS: Computer and information sciences
Discrete mathematics
Computer Science - Logic in Computer Science
D.2.4
F.1.1
F.1.3
Correctness
General Computer Science
Computer science
Natural number
Function (mathematics)
Computational Complexity (cs.CC)
Logic in Computer Science (cs.LO)
Theoretical Computer Science
Test (assessment)
Computer Science - Computational Complexity
Simple (abstract algebra)
Test functions for optimization
Subjects
Details
- ISSN :
- 03043975
- Volume :
- 802
- Database :
- OpenAIRE
- Journal :
- Theoretical Computer Science
- Accession number :
- edsair.doi.dedup.....c94e79675063a3b35e2a3992b561c858