{"id":"arxiv/2608.24045","url":"https://arxiv.org/abs/2608.24045","tags":["math.CO"],"score":0,"title":"Solution to an open problem on the computational complexity of immanant","domain":"math.CO","source":"arxiv","authors":["Xiangshuai Dong","Tingzeng Wu","Xing Gao"],"reviews":0,"subject":"math.CO","summary":"Immanants are a class of generalized matrix functions associated with the irreducible characters of the symmetric group. Bürgisser [SIAM J. Comput., 30 (2000), pp. 1023--1040] proved that the computation of hook immanants and immanants corresponding to rectangular Young diagrams of polynomially growing width is VNP-complete under $p$-projections. And he posed an open problem: whether the family of immanants corresponding to rectangular Young diagrams of width $2$ is VNP-complete under $p$-projections. This paper gives a solution to this problem. We prove that, over any field of…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-08-25","reactions":{}}