|
Ученые записки Ереванского государственного университета, серия Физические и Математические науки, 2011, выпуск 3, страницы 3–8
(Mi uzeru185)
|
|
|
|
Эта публикация цитируется в 1 научной статье (всего в 1 статье)
Mathematics
Polynomial length proofs for some class of Tseitin formulas
[О полиномиальных шагах выводов для некоторых классов формул Цейтина]
A. G. Abajian Chair of Discrete Mathematics and Theoretical Computer Science YSU, Armenia
Аннотация:
В настоящей работе введено понятие квазитрудноопределяемых формул и исследуются сложности выводов этих формул. Для некоторых классов квазитрудноопределяемых формул получены одинаковые по порядку верхние и нижние оценки шагов выводов в нескольких системах доказательств, основанных на дизъюнктивных нормальных формах (конъюнктивных нормальных формах).
Ключевые слова:
proof complexity, Split Tree, resolution system, resolution over linear equations, determinative conjunct, quasi-hard determinative formula.
Поступила в редакцию: 21.03.2011 Принята в печать: 20.04.2011
Образец цитирования:
A. G. Abajian, “Polynomial length proofs for some class of Tseitin formulas”, Уч. записки ЕГУ, сер. Физика и Математика, 2011, no. 3, 3–8
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/uzeru185 https://www.mathnet.ru/rus/uzeru/y2011/i3/p3
|
Статистика просмотров: |
Страница аннотации: | 127 | PDF полного текста: | 30 | Список литературы: | 32 |
|