permanent 와 determinant

행렬식(determinant)은 행과 열에서 하나씩 고른 원소의 곱을 부호를 붙여 더한 것이고, 퍼머넌트(permanent)는 부호 없이 모두 더한 것이다. 행렬식은 소거법으로 다항 시간에 계산되지만, 퍼머넌트는 원소가 0 과 1 뿐이어도 계산하기가 NP-완전 문제 이상으로 어렵다(#P-완전, 밸리언트 1979). 밸리언트는 n×n 퍼머넌트를 다항 크기 행렬의 행렬식으로 나타낼 수 없으리라고 추측했는데, 이것이 P 대 NP 의 대수적 판본이다. 지금까지 증명된 것은 필요한 행렬의 크기가 n²/2 이상이라는 정도다.