  We show that there is a polynomial space algorithm that counts the number of
perfect matchings in an $n$-vertex graph in $O^*(2^{n/2})\subset O(1.415^n)$
time. ($O^*(f(n))$ suppresses functions polylogarithmic in $f(n)$).The
previously fastest algorithms for the problem was the exponential space
$O^*(((1+\sqrt{5})/2)^n) \subset O(1.619^n)$ time algorithm by Koivisto, and
for polynomial space, the $O(1.942^n)$ time algorithm by Nederlof. Our new
algorithm's runtime matches up to polynomial factors that of Ryser's 1963
algorithm for bipartite graphs. We present our algorithm in the more general
setting of computing the hafnian over an arbitrary ring, analogously to Ryser's
algorithm for permanent computation.
  We also give a simple argument why the general exact set cover counting
problem over a slightly superpolynomial sized family of subsets of an $n$
element ground set cannot be solved in $O^*(2^{(1-\epsilon_1)n})$ time for any
$\epsilon_1>0$ unless there are $O^*(2^{(1-\epsilon_2)n})$ time algorithms for
computing an $n\times n$ 0/1 matrix permanent, for some $\epsilon_2>0$
depending only on $\epsilon_1$.
