Skip to main content

Research Repository

Advanced Search

Logical and complexity-theoretic aspects of models of computation with restricted access to arrays

Stewart, I.A.

Logical and complexity-theoretic aspects of models of computation with restricted access to arrays Thumbnail


Authors



Contributors

S.B. Cooper
Editor

T.F. Kent
Editor

B. Löwe
Editor

A. Sorbi
Editor

Abstract

We study a class of program schemes, NPSB, in which, aside from basic assignments, non-deterministic guessing and while loops, we have access to arrays; but where these arrays are binary write-once in that they are initialized to 'zero' and can only ever be set to 'one'. We show, amongst other results, that: NPSB can be realized as a vectorized Lindstr\"{o}m logic; there are problems accepted by program schemes of NPSB that are not definable in the bounded-variable infinitary logic $\mathcal{L}^\omega_{\infty\omega}$; all problems accepted by the program schemes of NPSB have asymptotic probability $1$; and on ordered structures, NPSB captures the complexity class $\mbox{{\bf L}}^{\mbox{\scriptsize{\bf NP}\normalsize}}$. We give equivalences (on the class of all finite structures) of the complexity-theoretic question 'Does $\mathbf{NP}$ equal $\mathbf{PSPACE}$?', where the logics and classes of program schemes involved in the equivalent statements define or accept only problems with asymptotic probability $0$ or $1$ and so do not cover many computationally trivial problems. The class of program schemes NPSB is actually the union of an infinite hierarchy of classes of program schemes. Finally, when we amend the semantics of our program schemes slightly, we find that the classes of the resulting hierarchy capture the complexity classes $\Sigma^p_i$ (where $i\geq 2$) of the Polynomial Hierarchy {\bf PH}.

Citation

Stewart, I. (2009). Logical and complexity-theoretic aspects of models of computation with restricted access to arrays. Journal of Logic and Computation, 19(1), 217-242. https://doi.org/10.1093/logcom/exn025

Journal Article Type Article
Publication Date Feb 1, 2009
Deposit Date Jun 29, 2009
Publicly Available Date Jun 29, 2009
Journal Journal of Logic and Computation
Print ISSN 0955-792X
Electronic ISSN 1465-363X
Publisher Oxford University Press
Peer Reviewed Peer Reviewed
Volume 19
Issue 1
Pages 217-242
DOI https://doi.org/10.1093/logcom/exn025
Keywords Finite model theory, Descriptive complexity, Program schemes.
Publisher URL http://www.dur.ac.uk/i.a.stewart/Papers/logcapPH.pdf

Files





You might also like



Downloadable Citations