A note on the permanent value problem

DOI10.1016/0020-0190(92)90021-MzbMath0780.68067OpenAlexW2012706785WikidataQ127321120 ScholiaQ127321120MaRDI QIDQ1198001

Sanjeev Saluja

Publication date: 16 January 1993

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(92)90021-m

zbMATH Keywords

computational complexityinteger matricespermanentcounting classes

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Determinants, permanents, traces, other special matrix functions (15A15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Matrices of integers (15B36)

Related Items

Some upper bounds for permanents of (0, 1)-matrices, Relationships among $PL$, $\#L$, and the determinant, Efficient computation of the permanent of a sparse matrix, Unnamed Item

Cites Work

• The complexity of computing the permanent
• The complexity of combinatorial problems with succinct input representation
• The polynomial-time hierarchy
• PP is as Hard as the Polynomial-Time Hierarchy
• Computational Complexity of Probabilistic Turing Machines
• Computational Work and Time on Finite Machines
• The complexity of theorem-proving procedures