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

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

2001-12-03

arxiv.org/abs/cs/0112002v1

Computer Science

Logic in Computer Science

Scientific paper

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 Lindstrom logic; there are problems accepted by program schemes of NPSB that are not definable in the bounded-variable infinitary logic ${\cal L}^\omega_{\infty\omega}$; all problems accepted by the program schemes of NPSB have a zero-one law; and on ordered structures, NPSB captures the complexity class $[ L]^[{\scriptsize NP\normalsize}]$. The class of program schemes NPSB is actually the union of an infinite hierarchy of classes of program schemes. 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 1$) of the Polynomial Hierarchy PH. Finally, we give logical equivalences of the complexity-theoretic question `Does NP equal PSPACE?' where the logics (and classes of program schemes) involved define only problems with zero-one laws (and so do not define some computationally trivial problems).

Affiliated with

Also associated with

No associations

Rating

Program schemes with binary write-once arrays and the complexity classes they capture does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Program schemes with binary write-once arrays and the complexity classes they capture, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Program schemes with binary write-once arrays and the complexity classes they capture will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-235000