Результаты исследований: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › Рецензирование
We consider satisfiable Tseitin formulas TSG,c based on d-regular expanders G with the absolute value of the second largest eigenvalue less than d3 . We prove that any nondeterministic read-once branching program (1-NBP) representing TSG,c has size 2(n), where n is the number of vertices in G. It extends the recent result by Itsykson at el. [9] from OBDD to 1-NBP. On the other hand it is easy to see that TSG,c can be represented as a read-2 branching program (2-BP) of size O(n), as the negation of a nondeterministic read-once branching program (1-coNBP) of size O(n) and as a CNF formula of size O(n). Thus TSG,c gives the best possible separations (up to a constant in the exponent) between 1-NBP and 2-BP, 1-NBP and 1-coNBP and between 1-NBP and CNF.
| Язык оригинала | английский |
|---|---|
| Название основной публикации | 42nd International Symposium on Mathematical Foundations of Computer Science, MFCS 2017 |
| Редакторы | Kim G. Larsen, Jean-Francois Raskin, Hans L. Bodlaender |
| Издатель | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing |
| ISBN (электронное издание) | 9783959770460 |
| DOI | |
| Состояние | Опубликовано - 1 ноя 2017 |
| Событие | 42nd International Symposium on Mathematical Foundations of Computer Science, MFCS 2017 - Aalborg, Дания Продолжительность: 21 авг 2017 → 25 авг 2017 |
| Название | Leibniz International Proceedings in Informatics, LIPIcs |
|---|---|
| Том | 83 |
| ISSN (печатное издание) | 1868-8969 |
| конференция | 42nd International Symposium on Mathematical Foundations of Computer Science, MFCS 2017 |
|---|---|
| Страна/Tерритория | Дания |
| Город | Aalborg |
| Период | 21/08/17 → 25/08/17 |
ID: 49785281