On tractability of disjoint AND-decomposition of boolean formulas

Pavel Emelyanov, Denis Ponomaryov

Результат исследования: Публикации в книгах, отчётах, сборниках, трудах конференцийстатья в сборнике материалов конференциинаучнаярецензирование

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

Аннотация

Disjoint AND-decomposition of a boolean formula means its representation as a conjunction of two (or several) formulas having disjoint sets of variables. We show that deciding AND-decomposability is intractable in general for boolean formulas given in CNF or DNF and prove tractability of computing AND-decompositions of boolean formulas given in positive DNF, Full DNF, and ANF. The results follow from tractability of multilinear polynomial factorization over the finite field of order 2, for which we provide a polytime factorization algorithm based on identity testing for partial derivatives of multilinear polynomials.

Язык оригиналаанглийский
Название основной публикацииPerspectives of System Informatics - 9th International Ershov Informatics Conference, PSI 2014, Revised Selected Papers
ИздательSpringer-Verlag GmbH and Co. KG
Страницы92-101
Число страниц10
ISBN (печатное издание)9783662468227
DOI
СостояниеОпубликовано - 1 янв 2015
Опубликовано для внешнего пользованияДа
Событие9th International Ershov Informatics Conference on Perspectives of System Informatics, PSI 2014 - St. Petersburg, Российская Федерация
Продолжительность: 24 июн 201427 июн 2014

Серия публикаций

НазваниеLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Том8974
ISSN (печатное издание)0302-9743
ISSN (электронное издание)1611-3349

Конференция

Конференция9th International Ershov Informatics Conference on Perspectives of System Informatics, PSI 2014
СтранаРоссийская Федерация
ГородSt. Petersburg
Период24.06.201427.06.2014

Fingerprint Подробные сведения о темах исследования «On tractability of disjoint AND-decomposition of boolean formulas». Вместе они формируют уникальный семантический отпечаток (fingerprint).

  • Цитировать

    Emelyanov, P., & Ponomaryov, D. (2015). On tractability of disjoint AND-decomposition of boolean formulas. В Perspectives of System Informatics - 9th International Ershov Informatics Conference, PSI 2014, Revised Selected Papers (стр. 92-101). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Том 8974). Springer-Verlag GmbH and Co. KG. https://doi.org/10.1007/978-3-662-46823-4_8