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.