We consider the complexity of Δ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 PSPACEcomplete. Thus, the complexity results indicate the analogy between the truth problem for Δ0 formulas with conditional terms and the truth problem for quantified boolean formulas.
Предметные области OECD FOS+WOS
- 1.01 МАТЕМАТИКА