\#P-hardness of computing matrix immanants are proved for each member of a broad class of shapes and restricted sets of matrices. We prove \#P-hardness of computing $\lambda$-immanants of $0$-$1$ matrices when $\lambda$ has a large domino-tilable part and satisfying some technical conditions. We also give hardness proofs of some $\lambda$-immanants of weighted adjacency matrices of planarly drawable directed graphs, such that the shape $\lambda = (\mathbf{1}+\lambda_d)$ has size $n$ such that $|\lambda_d| = n^{\varepsilon}$ for some $0<\varepsilon<\frac{1}{2}$, and for some $w$, the shape $\lambda_d/(w)$ is tilable with $1\times 2$ dominos.
翻译：证明了在一类广泛的形状和受限制的矩阵集中，计算矩阵因子式的#P难度。我们证明了当$\lambda$具有大型多米诺可铺砌部分且满足一些技术条件时，计算$0$-$1$矩阵的$\lambda$-因子式的#P难度。我们还给出了一些$\lambda$-因子式的难度证明，这些因子式适用于可平面绘制的有向图的带权邻接矩阵，其中形状$\lambda=(\mathbf{1}+\lambda_d)$的大小为$n$，使得$|\lambda_d|=n^{\varepsilon}$，其中$0<\varepsilon<\frac{1}{2}$，并且对于某些$w$，形状$\lambda_d/(w)$可用$1\times 2$多米诺骨牌铺平。
相关内容
微信扫码咨询专知VIP会员