פרמננטה – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
מ בוט: מעביר קישורי בינויקי לויקינתונים - d:q1344007 |
הרחבה |
||
שורה 2:
: <math> per(A) = \sum_{\sigma \in S_n} \prod_{i=1}^n A_{i, \sigma(i)}</math>,
כאשר הסכום הוא על-פני התמורות <math>\ \sigma \in S_n</math> ב[[חבורת התמורות]]. בפרט, הפרמננטה של מטריצה שרכיביה חיוביים, גם היא חיובית. הפרמננטה הופיעה לראשונה במאמר שכתב [[אוגוסטין לואי קושי]], ב-[[1812]].
דוגמה:
:<math>\operatorname{perm}\begin{pmatrix}a&b \\ c&d\end{pmatrix}=ad+bc,</math>
וכן:
:<math>\operatorname{perm}\begin{pmatrix}a&b&c \\ d&e&f \\ g&h&i \end{pmatrix}=aei + bfg + cdh + ceg + bdi + afh.</math>
בעוד שלדטרמיננטה יש משמעות גאומטרית והיא קשורה ישירות בפתרון [[מערכת משוואות לינארית|משוואות לינאריות]] (על-פי [[נוסחת קרמר]]), הפרמננטה שימושית בהקשרים שונים לחלוטין, כגון חישובי הסתברויות וספירת מסלולים בגרפים. שימוש נוסף הוא בעיית מציאת מספר ה[[שידוך מושלם|שידוכים המושלמים]] ב[[גרף דו צדדי]]. הבדל בולט אחר הוא העבודה שנדרש להשקיע בכל חישוב. למרות שבשני המקרים התוצאה תלויה ב-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#]] והיא שלמה עבורה. מאידך ידוע אלגוריתם פולינומי אקראי לקירוב הפרמננטה.
| |||