« first day (4 days earlier)    last day (3625 days later) » 

vzn
vzn
6:37 PM
interesting paper of the moment:
what I like about this is how it studies the clause graph of SAT, which have always thought is crucial to understanding hardness.
my main quibble is that it doesnt seem to estimate how many instances at random have bounded treewidth ie fit into its framework. are they common? rare?
they say in the close that the class is "large" as described in the introduction, but cant quite follow where it has this in the intro.
"We have described a cubic-time algorithm solving SAT and #SAT for a large class of instances,
namely those CNF formulas F that have a strong backdoor set of size at most k into the class of
formulas with incidence treewidth at most t, where k and t are constants. As illustrated in the
introduction, this class of instances is larger than the class of all formulas with bounded incidence
treewidth."
 

« first day (4 days earlier)    last day (3625 days later) »