Geodesic
On the complexity of formulas in semantic programming
Sibirskie èlektronnye matematičeskie izvestiâ, Tome 15 (2018), pp. 987-995

Voir la notice de l'article provenant de la source Math-Net.Ru

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.
Keywords: semantic programming, polynomial time/space complexity, $\Delta_0$-formulas.
Mots-clés : list structures 
@article{SEMR_2018_15_a24,
     author = {S. Ospichev and D. Ponomarev},
     title = {On the complexity of formulas in semantic programming},
     journal = {Sibirskie \`elektronnye matemati\v{c}eskie izvesti\^a},
     pages = {987--995},
     publisher = {mathdoc},
     volume = {15},
     year = {2018},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/SEMR_2018_15_a24/}
}
TY  - JOUR
AU  - S. Ospichev
AU  - D. Ponomarev
TI  - On the complexity of formulas in semantic programming
JO  - Sibirskie èlektronnye matematičeskie izvestiâ
PY  - 2018
SP  - 987
EP  - 995
VL  - 15
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SEMR_2018_15_a24/
LA  - en
ID  - SEMR_2018_15_a24
ER  - 
%0 Journal Article
%A S. Ospichev
%A D. Ponomarev
%T On the complexity of formulas in semantic programming
%J Sibirskie èlektronnye matematičeskie izvestiâ
%D 2018
%P 987-995
%V 15
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SEMR_2018_15_a24/
%G en
%F SEMR_2018_15_a24
S. Ospichev; D. Ponomarev. On the complexity of formulas in semantic programming. Sibirskie èlektronnye matematičeskie izvestiâ, Tome 15 (2018), pp. 987-995. http://geodesic.mathdoc.fr/item/SEMR_2018_15_a24/