Sharp-P
מתוך ויקיפדיה, האנציקלופדיה החופשית
במדעי המחשב, P# (קרי: Sharp-P) היא מחלקת סיבוכיות המכילה את אוסף בעיות הספירה הקשורות לבעיות ההכרעה השייכות למחלקה NP.
תוכן עניינים |
[עריכה] מבוא
בעיות רבות במדעי המחשב מנוסחת כבעיות הכרעה - בעיות שהתשובה להן היא "כן" או "לא". למשל, האם ניתן לבחור תת קבוצה של קבוצת מספרים נתונה כך שאיבריה יסתכמו ל-0, האם עבור רשת כבישים שמחברת ערים קיים מסלול שמבקר בכל הערים, ובכל עיר בדיוק פעם אחת (זוהי הבעיה של מציאת מסלול המילטוני בגרף), האם פסוק לוגי כלשהו הוא ספיק (כלומר, יכול לקבל ערך אמת) וכדומה.
על בעיות מסוג זה ניתן לענות בקלות יחסית (כלומר, בחישוב המתבצע בזמן ריצה פולינומי) אם נתון פתרון עבורן - למשל, שאלת המסלול ההמילטוני נענית מיד אם מישהו מציג מסלול שכזה, שכן כל שיש לעשות הוא לבדוק שהמסלול שהוצג הוא אכן חוקי (מבקר בכל הערים ולא מבקר באף עיר פעמיים). אוסף הבעיות שבדיקת פתרון מוצע עבורן היא קלה נקרא NP.
המחלקה P# עוסקת בשאלה מורכבת יותר: לא רק האם קיים או לא קיים פתרון, אלא כמה פתרונות קיימים. בגרף יכול להיות יותר ממסלול המילטוני אחד, והבעיה המתאימה לבעיית המסלול ההמילטוני ב-P# שואלת כמה מסלולים שונים קיימים.
מכיוון שתשובה לבעיה הכמותית גוררת מיד תשובה לבעיית ההכרעה (אם קיים לפחות מסלול המילטוני אחד התשובה היא חיובית, ורק אם קיימים אפס התשובה היא שלילית) הבעיות הנמצאות ב-P# הן קשות לפחות כמו הבעיות המקבילות להן ב-NP. בפרט, קיימות בעיות ב-NP אשר ידוע להן פתרון יעיל, אך לבעיות המקבילות להן ב-P# לא ידוע פתרון יעיל.
[עריכה] הגדרה פורמלית
ההגדרה הפורמלית של P# מבוססת על המושג של מכונת טיורינג אי דטרמיניסטית. היא מוגדרת כמחלקת כל הפונקציות מהמספרים הטבעיים לעצמם המקיימות את התכונה הבאה:
הפונקציה f שייכת ל-P# אם קיימת מכונת טיורינג אי דטרמיניסטית שמספר מסלולי החישוב המקבלים שלה על קלט מסוים שווה לערך ש-f מחזירה עליו. בניסוח פורמלי: קיימת M כך שאם 
, אז קיימים ל-M בדיוק y מסלולי חישוב מקבלים על הקלט x.
למשל, עבור הבעיה SAT#, שהיא בעיית הספירה של מספר ההשמות המספקות של פסוק לוגי, קיימת מכונת טיורינג כדלהלן: בהינתן הפסוק x, המכונה מנחשת השמה כלשהי, בודקת אם ההשמה מספקת את x ועונה בהתאם. למכונה זו קיים מסלול חישוב מקבל לכל השמה מספקת של x, וכל מסלול חישוב מקבל מתאים להשמה שכזו, ולכן מספר מסלולי החישוב המקבלים על x במכונה זו הוא בדיוק מספר ההשמות המספקות את x.
[עריכה] תכונות
בדומה למושג השלמות שקיים עבור המחלקה NP, כך קיים גם מושג של שלמות ב-P#. כלומר, קיימות בעיות ב-P# שפתרון יעיל עבורן יבטיח פתרון יעיל לכל שאר הבעיות ב-P#.
בעיות ספירה רבות שגרסת ההכרעה שלהן היא NP-שלמה הן גם שלמות ב-P#. כך, למשל, SAT# - בהינתן נוסחה מה מספר ההשמות המספקות שלה - היא P#-שלמה, וגרסת בעיית ההכרעה שלה, בעיית SAT, היא בעיה NP-שלמה ידועה על פי משפט קוק-לוין. אולם קיימות מספר בעיות שגרסת ההכרעה שלהן היא בP בעוד גרסת הספירה היא P#-שלמה. כך למשל בעיית מציאת מספר השידוכים המושלמים בגרף דו צדדי היא P#-שלמה, בעוד שבעית ההכרעה המקבילה לה - השאלה האם בגרף דו צדדי קיים שידוך מושלם - ניתנת לפתרון יעיל, כלומר ידוע שהיא שייכת ל-P. בעית ספירת השידוכים המושלמים היא הבעיה של חישוב פרמננטה של מטריצה שערכיה הן רק 0 ו-1 ולכן גם הבעיה הזאת היא P#-שלמה. פתרון כל אחת מהבעיות שהן P#-שלמות בזמן יעיל יגרור בפרט את קיום השוויון P=NP.
ממשפט טודה עולה כי ההיררכייה הפולינומית PH מוכלת ב-
. כלומר, כל בעיה השייכת להיררכייה הפולינומית ניתן לפתרון בזמן פולינומי באמצעות אורקל לפתרון בעיה ב-P#.
[עריכה] קישורים חיצוניים
- P# מתוך Complexity Zoo.
[עריכה] לקריאה נוספת
- Leslie G. Valiant (1979). "The Complexity of Computing the Permanent". Theoretical Computer Science 8: 189-201
- Ben-Dor, Amir and Halevi, Shai. (1993). "Zero-one permanent is #P-complete, a simpler proof". Proceedings of the 2nd Israel Symposium on the Theory and Computing Systems, 108-117.
