On the complexity of formulas in semantic programming

We consider the complexity of $\Delta_0$ formulas augmented with conditional terms. We show that for formulas having $n$ bounded quantifiers, for a fixed $n$, deciding the truth in a list superstructure with polynomial computable basic operations is of polynomial complexity. When the quantifier prefix has $n$ alternations of quantifiers, the truth problem is complete for the $n$-th level of the polynomial-time hierarchy. Under no restrictions on the quantifier prefix the truth problem is PSPACE-complete. Thus, the complexity results indicate the analogy between the truth problem for $\Delta_0$ formulas with conditional terms and the truth problem for quantified boolean formulas.