Logical Definability Versus Computational Complexity: Another Equivalence

We examine two different classes of program schemes involving arrays, one class, NPSA(1), allowing arrays in their full generality and the other, NPSB(1), only allowing arrays in a (syntactically) restricted form. Our main result is that the open question of whether the complexity class PSPACE is equal to the complexity class NP is equivalent to whether the class of problems (accepted by the program schemes of) NPSA(1) is equal to the class of problems (accepted by the program schemes of) NPSB(1). This is surprising because the class of problems NPSA(1) (which contains NPSB(1)) has a zero-one law. We go on to show that the PSPACE versus NP question is also equivalent to whether the positive unnested fragments of two particular vectorized Lindstrom logics are equally expressive (the full vectorized Lindstrom logics have zero-one laws too). Interestingly, the logics and classes of program schemes studied in this paper are not fragments of bounded-variable infinitary logic and consequentl..