We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.

Durham Research Online
You are in:

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

Stewart, I. A. (2009) 'Logical and complexity-theoretic aspects of models of computation with restricted access to arrays.', Journal of logic and computation., 19 (1). pp. 217-242.


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}.

Item Type:Article
Additional Information:An extended abstract of this paper appeared in: Proc. of Computation and Logic in the Real World, Third Conference on Computability in Europe (CiE 2007) (ed. S.B. Cooper, T.F. Kent, B. Löwe, A. Sorbi) (2007) 324-331.
Keywords:Finite model theory, Descriptive complexity, Program schemes.
Full text:(AM) Accepted Manuscript
Download PDF
Publisher Web site:
Date accepted:No date available
Date deposited:29 June 2009
Date of first online publication:February 2009
Date first made open access:No date available

Save or Share this output

Look up in GoogleScholar