Standard

On the complexity of formulas in semantic programming. / Ospichev, Sergey; Ponomarev, Denis.

In: Сибирские электронные математические известия, Vol. 15, 01.01.2018, p. 987-995.

Research output: Contribution to journal › Article › peer-review

Harvard

Ospichev, S & Ponomarev, D 2018, 'On the complexity of formulas in semantic programming', Сибирские электронные математические известия, vol. 15, pp. 987-995. https://doi.org/10.17377/semi.2018.15.083

APA

Ospichev, S., & Ponomarev, D. (2018). On the complexity of formulas in semantic programming. Сибирские электронные математические известия, 15, 987-995. https://doi.org/10.17377/semi.2018.15.083

Vancouver

Ospichev S, Ponomarev D. On the complexity of formulas in semantic programming. Сибирские электронные математические известия. 2018 Jan 1;15:987-995. doi: 10.17377/semi.2018.15.083

Author

Ospichev, Sergey ; Ponomarev, Denis. / On the complexity of formulas in semantic programming. In: Сибирские электронные математические известия. 2018 ; Vol. 15. pp. 987-995.

BibTeX

@article{cf1d0e7e4a92471eb7d415929da7b8ff,
title = "On the complexity of formulas in semantic programming",
abstract = "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.",
keywords = "List structures, Polynomial time/space complexity, Semantic programming, Δ-formulas, semantic programming, list structures, Delta(0)-formulas, polynomial time/space complexity",
author = "Sergey Ospichev and Denis Ponomarev",
year = "2018",
month = jan,
day = "1",
doi = "10.17377/semi.2018.15.083",
language = "English",
volume = "15",
pages = "987--995",
journal = "Сибирские электронные математические известия",
issn = "1813-3304",
publisher = "Sobolev Institute of Mathematics",

}

RIS

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 -

ID: 19262311