Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Tuesday, November 15, 2005, 12:15 pm
Duration: This information is not available in the database
Location: This information is not available in the database
Speaker: Andreas Razen
2SAT, the satisfiability problem of CNF formulas whose clauses contain at most two literals, is known to be solvable in polynomial time. However, its associated counting problem #2SAT of determining the number of satisfying assignments an (<= 2)-CNF formula can have, is #P-complete.
We describe a method for weighting formulas that allows improved running times of the form O(2cn) with c < 1 (n being the number of variables involved) suppressing polynomial factors, with the best current bound due to Fürer and Kasiviswanathan.
Additionally, we give a subclass of #2SAT instances that is solvable in linear time O(n).
Automatic MiSe System Software Version 1.4803M | admin login