On the complexity of formulas in semantic programming

Результат исследования: Научные публикации в периодических изданияхстатья

6 Цитирования (Scopus)

Аннотация

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.

Язык оригиналаанглийский
Страницы (с-по)987-995
Число страниц9
ЖурналSiberian Electronic Mathematical Reports
Том15
DOI
СостояниеОпубликовано - 1 янв 2018

Fingerprint Подробные сведения о темах исследования «On the complexity of formulas in semantic programming». Вместе они формируют уникальный семантический отпечаток (fingerprint).

  • Цитировать