Program schemes with binary write-once arrays and the complexity classes they capture

Iain A. Stewart

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…