Holographic Approximation: Difference between revisions
Jump to navigation
Jump to search
imported>Etone (Created page with "=Holant Problem =") |
imported>Etone No edit summary |
||
| Line 1: | Line 1: | ||
=Holant Problem = | =Holant Problem = | ||
== Recursion on tree == | |||
<math> | |||
\begin{align} | |||
\#\{\sigma_T\mid\sigma_T(e)=0\} | |||
&= | |||
\sum_{\ell=0}^k\sum_{S\in{[k]\choose \ell}}f_\ell \prod_{i\in S}\#\{\sigma_{T_i}\mid \sigma_{T_i}(e_i)=1\}\prod_{i\in [k]\setminus S}\#\{\sigma_{T_i}\mid \sigma_{T_i}(e_i)=0\}\\ | |||
\#\{\sigma_T\mid\sigma_T(e)=1\} | |||
&= | |||
\sum_{\ell=0}^k\sum_{S\in{[k]\choose \ell}}f_{\ell+1} \prod_{i\in S}\#\{\sigma_{T_i}\mid \sigma_{T_i}(e_i)=1\}\prod_{i\in [k]\setminus S}\#\{\sigma_{T_i}\mid \sigma_{T_i}(e_i)=0\} | |||
\end{align} | |||
</math> | |||
Revision as of 20:38, 17 April 2012
Holant Problem
Recursion on tree
[math]\displaystyle{ \begin{align} \#\{\sigma_T\mid\sigma_T(e)=0\} &= \sum_{\ell=0}^k\sum_{S\in{[k]\choose \ell}}f_\ell \prod_{i\in S}\#\{\sigma_{T_i}\mid \sigma_{T_i}(e_i)=1\}\prod_{i\in [k]\setminus S}\#\{\sigma_{T_i}\mid \sigma_{T_i}(e_i)=0\}\\ \#\{\sigma_T\mid\sigma_T(e)=1\} &= \sum_{\ell=0}^k\sum_{S\in{[k]\choose \ell}}f_{\ell+1} \prod_{i\in S}\#\{\sigma_{T_i}\mid \sigma_{T_i}(e_i)=1\}\prod_{i\in [k]\setminus S}\#\{\sigma_{T_i}\mid \sigma_{T_i}(e_i)=0\} \end{align} }[/math]