Program Schemes with Binary Write-Once Arrays: Their Complexity Classes and Implications

Title: Program Schemes with Binary Write-Once Arrays: Their Complexity Classes and Implications

Abstract: This research article explores a class of program schemes called NPSB, where the main feature is the use of binary write-once arrays. These arrays are initialized to '0' and can only be set to '1'. The study reveals several interesting results and implications.

1. NPSB can be realized as a vectorized Lindström logic, which is a common method used in descriptive complexity theory. 2. The article shows that there are problems accepted by program schemes of NPSB that are not definable in the bounded-variable infinitary logic Lω∞ω. 3. All problems accepted by the program schemes of NPSB have a zero-one law, meaning that the probability of a correct answer is either 0 or 1. 4. On ordered structures, NPSB captures the complexity class LNP. 5. The article also introduces an infinite hierarchy of classes of program schemes, which is shown to capture the complexity classes Σp(i) of the Polynomial Hierarchy PH. 6. The research provides logical equivalences of the complexity-theoretic question 'Does NP equal PSPACE?' using the classes of program schemes and logics involved.

Implications: This research has significant implications for the field of descriptive complexity theory and computational complexity. It provides new insights into the expressive power of program schemes and their relationship with traditional logics. The results also have practical applications in the design and analysis of algorithms and data structures.

Link to Article: https://arxiv.org/abs/0112002v1 Authors: arXiv ID: 0112002v1