פרמננטה – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
יובל המאתיים שמח |
|||
שורה 1:
ב[[אלגברה לינארית]] וב[[קומבינטוריקה]], ה'''פרמננטה''' של [[מטריצה]] היא גודל מספרי, המחושב על-פי נוסחה דומה לזו של ה[[דטרמיננטה]]. בעוד שב[[חישוב]] הדטרמיננטה, הנפוץ בהרבה, יש לחבר ולחסר את המכפלות של אברי המטריצה לסירוגין, הפרמננטה מוגדרת כסכום של כל המכפלות, ללא חיסור:
: <math> per(A) = \sum_{\sigma \in S_n} \prod_{i=1}^n A_{i, \sigma(i)}</math>,
כאשר הסכום הוא על-פני התמורות <math>\ \sigma \in S_n</math> ב[[חבורת התמורות]]. בפרט, הפרמננטה של מטריצה שרכיביה חיוביים, גם היא חיובית. הפרמננטה הופיעה לראשונה במאמר שכתב [[אוגוסטין לואי קושי]], ב-[[1812]].
בעוד שלדטרמיננטה יש משמעות גאומטרית והיא קשורה ישירות בפתרון [[מערכת משוואות לינארית|משוואות לינאריות]] (על-פי [[נוסחת קרמר]]), הפרמננטה שימושית בהקשרים שונים לחלוטין, כגון חישובי הסתברויות וספירת מסלולים בגרפים. שימוש נוסף הוא בעיית מציאת מספר ה[[שידוך מושלם|שידוכים המושלמים]] ב[[גרף דו צדדי]]. הבדל בולט אחר הוא העבודה שנדרש להשקיע בכל חישוב. למרות שבשני המקרים התוצאה תלויה ב-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#]] והיא שלמה עבורה. מאידך ידוע אלגוריתם פולינומי אקראי לקירוב הפרמננטה.
| |||