We establish the $\#P$-hardness of computing a broad class of immanants, even when restricted to specific categories of matrices. Concretely, we prove that computing $λ$-immanants of $0$-$1$ matrices is $\#P$-hard whenever the partition~$λ$ contains a sufficiently large domino-tileable region, subject to certain technical conditions. We also give hardness proofs for some $λ$-immanants of weighted adjacency matrices of planar directed graphs, such that the shape $λ= (\mathbf{1} + λ_d)$ has size $n$ such that $|λ_d| = n^\varepsilon$ for some $0 < \varepsilon < \frac{1}{2}$, and such that for some $w$, the shape $λ_d/(w)$ is tileable with $1 \times 2$ dominos.
翻译:我们证明了计算一大类不变式的#P-困难性,即使限制在特定类型的矩阵上。具体而言,我们证明了当分区λ包含一个足够大的多米诺可铺砌区域(在满足特定技术条件下)时,计算0-1矩阵的λ-不变式是#P-困难的。我们还针对平面有向图的加权邻接矩阵的某些λ-不变式给出了困难性证明,其中形状λ = (1 + λ_d)的规模为n,使得|λ_d| = n^ε(其中0 < ε < 1/2),并且存在某个w使得形状λ_d/(w)可通过1×2多米诺骨牌铺砌。