Результаты исследований: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › научная › Рецензирование
Satisfiable tseitin formulas are hard for nondeterministic read-once branching programs. / Glinskih, Ludmila; Itsykson, Dmitry.
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, 2017. (Leibniz International Proceedings in Informatics, LIPIcs; Том 83).Результаты исследований: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › научная › Рецензирование
}
TY - GEN
T1 - Satisfiable tseitin formulas are hard for nondeterministic read-once branching programs
AU - Glinskih, Ludmila
AU - Itsykson, Dmitry
PY - 2017/11/1
Y1 - 2017/11/1
N2 - 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.
AB - 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.
KW - Expander
KW - Read-once branching program
KW - Tseitin formula
UR - http://www.scopus.com/inward/record.url?scp=85038419366&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.MFCS.2017.26
DO - 10.4230/LIPIcs.MFCS.2017.26
M3 - Conference contribution
AN - SCOPUS:85038419366
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 42nd International Symposium on Mathematical Foundations of Computer Science, MFCS 2017
A2 - Larsen, Kim G.
A2 - Raskin, Jean-Francois
A2 - Bodlaender, Hans L.
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 42nd International Symposium on Mathematical Foundations of Computer Science, MFCS 2017
Y2 - 21 August 2017 through 25 August 2017
ER -
ID: 49785281