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/

[1] Ershov Yu. L., Definability and computability, Consultants Bureau, New York, 1996 | MR | Zbl

[2] Barwise J., Admissible sets and structures, Springer, Berlin, 1975 | MR | Zbl

[3] Goncharov S. S., Sviridenko D. I., “$\Sigma$-programming”, Transl. II. Ser., Amer. Math. Soc., 142 (1989), 101–121 | MR | Zbl

[4] Goncharov S. S., Sviridenko D. I., “$\Sigma$-programming and its Semantics”, Vychisl. Systemy, 120 (1987), 24–51 (in Russian) | MR | Zbl

[5] Goncharov S. S., Sviridenko D. I., “Theoretical Aspects of $\Sigma$-programming”, Lect. Notes Comp. Sci., 215, 1986, 169–179 | DOI | MR | Zbl

[6] Ershov Yu. L., Goncharov S. S., Sviridenko D. I., “Semantic Programming”, Information processing 86, Proc. IFIP 10th World Comput. Congress, v. 10, Elsevier Sci., Dublin, 1986, 1093–1100 | MR | Zbl

[7] Ershov Yu. L., Goncharov S. S., Sviridenko D. I., “Semantic Foundations of Programming”, Fundamentals of Computation Theory, Proc. Intern. Conf. FCT 87 (Kazan), Lect. Notes Comp. Sci., 278, 1987, 116–122 | DOI | MR | Zbl

[8] Goncharov S. S., “Conditional Terms in Semantic Programming”, Siberian Mathematical Journal, 58:5 (2017), 794–800 | DOI | MR | Zbl

[9] S. Arora, B. Barak, Computational Complexity: a Modern Approach, Cambridge University Press, 2009 | MR | Zbl

[10] C.H. Papadimitriou, Computational complexity, Addison-Wesley, 1994 | MR | Zbl

[11] L. J. Stockmeyer, A. R. Meyer, “Word Problems Requiring Exponential Time”, Proc. Fifth Annual ACM Symposium on Theory of Computing (Austin, Texas, USA, 1973), 1–9 | MR

[12] A. A. Malykh, A. V. Mantsivoda, “Document models”, Vestnik of the Irkutsk State University, Ser. Matematika, 21 (2017), 89–-107 (in russian) | DOI | Zbl