Information

Event Records

12th CoRe Seminar

Date and time:  2021.06.21 Mon. 10:00-12:00
Venue:  Online
Speaker:  TAMAKI, Suguru (U. Hyogo, invited talk)
Title:  On the complexity of the connectivity of Boolean satisfiability (CONN-SAT)
Summary: 
CONN-SAT is the problem of deciding whether a subgraph of a Hamming cube is connected or not, where the subgraph is induced by a set of satisfying assignments of Boolean formulas. As the complexity of SAT varies according to types of formulas (Horn SAT, XOR SAT, 2SAT, 3SAT etc.), the complexity of CONN-SAT is classified by such types. In this talk, I will give an overview on the classification of the complexity of CONN-SAT. I also mention an exponential time algorithm for CONN-SAT where formulas are k-CNFs (the problem is PSPACE-complete). This is a joint work with Kazuhisa Makino and Masaki Yamamoto.
Update:2021.06.09