Sharp-P

במדעי המחשב, P# (קרי: Sharp-P) היא מחלקת סיבוכיות המכילה את אוסף בעיות הספירה הקשורות לבעיות ההכרעה השייכות למחלקה NP.

מבוא

בעיות רבות במדעי המחשב מנוסחות כבעיות הכרעה - בעיות שהתשובה להן היא "כן" או "לא". למשל, האם ניתן לבחור תת קבוצה של קבוצת מספרים נתונה כך שאיבריה יסתכמו ל-0, האם עבור רשת כבישים שמחברת ערים קיים מסלול שמבקר בכל הערים, ובכל עיר בדיוק פעם אחת (זוהי הבעיה של מציאת מסלול המילטוני בגרף), האם פסוק לוגי כלשהו הוא ספיק (כלומר, יכול לקבל ערך אמת) וכדומה.

על בעיות מסוג זה ניתן לענות בקלות יחסית (כלומר, בחישוב המתבצע בזמן ריצה פולינומי) אם נתון פתרון עבורן - למשל, שאלת המסלול ההמילטוני נענית מיד אם מישהו מציג מסלול שכזה, שכן כל שיש לעשות הוא לבדוק שהמסלול שהוצג הוא אכן חוקי (מבקר בכל הערים ולא מבקר באף עיר פעמיים). אוסף הבעיות שבדיקת פתרון מוצע עבורן היא קלה נקרא NP.

המחלקה P# עוסקת בשאלה מורכבת יותר: לא רק האם קיים או לא קיים פתרון, אלא כמה פתרונות קיימים. בגרף יכול להיות יותר ממסלול המילטוני אחד, והבעיה המתאימה לבעיית המסלול ההמילטוני ב-P# שואלת כמה מסלולים שונים קיימים.

מכיוון שתשובה לבעיה הכמותית גוררת מיד תשובה לבעיית ההכרעה (אם קיים לפחות מסלול המילטוני אחד התשובה היא חיובית, ורק אם קיימים אפס התשובה היא שלילית) הבעיות הנמצאות ב-P# הן קשות לפחות כמו הבעיות המקבילות להן ב-NP. בפרט, קיימות בעיות אשר ידוע להן פתרון יעיל, אך לבעיות המקבילות להן ב-P# לא ידוע פתרון יעיל.

הגדרה פורמלית

ההגדרה הפורמלית של P# מבוססת על המושג של מכונת טיורינג לא דטרמיניסטית. היא מוגדרת כקבוצת כל הפונקציות מהמספרים הטבעיים לעצמם המקיימות את התכונה הבאה:

הפונקציה f שייכת ל-P# אם קיימת מכונת טיורינג אי דטרמיניסטית שמספר מסלולי החישוב המקבלים שלה על קלט מסוים שווה לערך ש-f מחזירה עליו. בניסוח פורמלי: קיימת M כך שאם $\ f(x)=y$, אז קיימים ל-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 מוכלת ב-$\ \mathrm {P} ^{\#\mathrm {P} }$. כלומר, כל בעיה השייכת להיררכיה הפולינומית ניתן לפתרון בזמן פולינומי באמצעות אורקל לפתרון בעיה ב-P#.

בנוסף, ניתן להוכיח כי $\ \mathrm {P} ^{PP}=\ \mathrm {P} ^{\#\mathrm {P} }.$

ספירה מקורבת

כמו שראינו למעלה, בעיות ספירה הן בעיות קשות ביותר. לכן בדרך כלל כשנרצה לספור את מספר הפתרונות של בעיה מסוימת, נעדיף להשתמש בפתרון מקורב.

הגדרה של קירוב

פונקציה $f_{app}$ תיקרא c-מקרבת לפונקציה f אם לכל $x\in \{0,1\}^{*}$ מתקיים

${\frac {f(x)}{c}}\leq f_{app}(x)\leq c\cdot f(x)$

מקובל לדבר על ספירה מקורבת ראנדומית, כלומר $f_{app}$ תיקרא $(c,\epsilon )$ מקרבת לפונקציה f אם לכל $x\in \{0,1\}^{*}$ מתקיים

$\Pr {\bigl [}{\frac {f(x)}{c}}\leq f_{app}(x)\leq c\cdot f(x){\bigr ]}\geq 1-\epsilon$

עבור אפסילון כלשהו

ידוע שאם קיים לכל $f\in \#P$ $({\frac {1}{3}},10)$ קירוב אז $NP\subseteq BPP$

לקריאה נוספת

• 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.

קישורים חיצוניים

• #P מתוך Complexity Zoo.