2013/09/09 by Nicolas de Rugy-Altherre, de Rugy-Altherre, Nicolas
Computer Science · Mathematics · #Algebraic structures and combinatorial models #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Graph theory and applications #Markov Chains and Monte Carlo Methods #cs.CC
paper · pdf · doi:10.48550/arxiv.1309.2156
Initially published in CIE2013
arxiv created 2013/09/09 · openalex publication_date 2013/09/09 · arxiv updated 2013/09/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The fermionant can be seen as a generalization of both the permanent (for k=-1) and the determinant. We demonstrate that it is VNP-complete for most cases. Furthermore it is #P-complete for the cases. The immanant is also a generalization of the permanent (for a Young diagram with a single line) and of the determinant (when the Young diagram is a column). We demonstrate that the immanant of any family of Young diagrams with bounded width and at least n boxes at the right of the first column is VNP-complete.