פרמננטה – הבדלי גרסאות

בעוד שלדטרמיננטה יש משמעות גאומטרית והיא קשורה ישירות בפתרון [[מערכת משוואות לינארית|משוואות לינאריות]] (על-פי [[נוסחת קרמר]]), הפרמננטה שימושית בהקשרים שונים לחלוטין, כגון חישובי הסתברויות וספירת מסלולים בגרפים. שימוש נוסף הוא בעיית מציאת מספר ה[[שידוך מושלם|שידוכים המושלמים]] ב[[גרף דו צדדי]]. הבדל בולט אחר הוא העבודה שנדרש להשקיע בכל חישוב. למרות שבשני המקרים התוצאה תלויה ב-n [[עצרת]] מכפלות, את הדטרמיננטה אפשר לחשב בכ- <math>\ n^3</math> פעולות באמצעות [[דירוג מטריצות|דירוג]] המטריצה המדוברת (ואף מהר יותר, באמצעות כפל מטריצות מהיר). לעומת זאת, לא ידועה שיטה מהירה לחישוב הפרמננטה. סיכום כל המכפלות השונות בזו אחר זו יהיה כרוך ב <math>\ {n!}</math> פעולות וסיבוכיות האלגוריתם המהיר ביותר הידוע היא <math>\ {O(n2^n)}</math>. יתירה מזאת, [[לזלי ואלינט]] הראה שאםשזו בעיה [[NP-שלמה]]. כלומר אם קיים אלגוריתם עם סיבוכיות פולינומית לחישוב של הפרמננטה, ינבע מכך כי [[P=NP]], והדבר נכון אף למטריצות שאבריהן הן <math>\ 0</math> או <math>\ 1</math>. בעיית חישוב הפרמננטה שייכת ל[[מחלקות סיבוכיות|מחלקת הסיבוכיות]] [[Sharp-P|P#]] והיא שלמה עבורה. מאידך ידוע אלגוריתם פולינומי אקראי לקירוב הפרמננטה.