TY - JOUR

T1 - On the complexity of formulas in semantic programming

AU - Ospichev, Sergey

AU - Ponomarev, Denis

PY - 2018/1/1

Y1 - 2018/1/1

N2 - 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.

AB - 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.

KW - List structures

KW - Polynomial time/space complexity

KW - Semantic programming

KW - Δ-formulas

KW - semantic programming

KW - list structures

KW - Delta(0)-formulas

KW - polynomial time/space complexity

UR - http://www.scopus.com/inward/record.url?scp=85059758262&partnerID=8YFLogxK

U2 - 10.17377/semi.2018.15.083

DO - 10.17377/semi.2018.15.083

M3 - Article

AN - SCOPUS:85059758262

VL - 15

SP - 987

EP - 995

JO - Сибирские электронные математические известия

JF - Сибирские электронные математические известия

SN - 1813-3304

ER -