P/Poly

P/Poly היא מחלקת סיבוכיות חשובה במדעי המחשב שכוללת את הבעיות שניתן לפתור בזמן פולינומי באמצעות מחרוזות עצה פולינומיות באורך הקלט.

המחלקה P/Poly כוללת בתוכה בעיות שאינן כריעות. קל לראות את האמור על ידי הגרסה האונארית של בעיית העצירה. בעיית העצירה אינה כריעה ולכן גם הגרסה האונארית שלה אינה כריעה, אך עבור כל קלט חוקי $1^{n}$ מספיק להשתמש בביט אחד של עצה על מנת להכריע אם המילה בשפה או לא, שהרי כל מילה שאינה מהצורה $1^{n}$ אינה בשפה, והמילה $1^{n}$ בשפה אם ורק אם ביט העצה שווה ל-1.

מן האמור לעיל, קל לראות שכל שפה דלילה מוכלת ב-P/Poly, ואף ניתן לראות שכל שפה אונארית מוכלת ב-P/1, ובפרט ב-P/Poly.

השאלה האם המחלקה NP מוכלת במחלקה P/Poly היא בעיה פתוחה, אשר תשובה חיובית תוביל לקריסת ההיררכיה הפולינומית לדרגה 2 (משפט קארפ-ליפטון), כלומר $PH=\Sigma _{2}$. אם P/Poly מכילה את PSPACE אז PSPACE=AM.

הגדרה נוספת ל-P/Poly, היא על ידי מעגלים בוליאניים, כלומר שפה L נמצאת ב-P/Poly אם ורק אם קיימת משפחת מעגלים בוליאנים ${\{C_{n}\}}_{n=1}^{\infty }$ שמכריעה אותה, כך שגודל כל מעגל פולינומי בגודל הקלט.

משפט אדלמן קובע כי המחלקה BPP, מחלקת הבעיות הפתירות על ידי אלגוריתם אקראי בעל זמן ריצה פולינומי, אשר צודק בהסתברות 2/3 לפחות, ידועה להיות מוכלת ב-P/Poly. זו התוצאה הבסיסית בדרנדומיזציה, תחום החוקר מתי אפשר להפוך אלגוריתמים מאקראיים ללא אקראיים (דטרמיניסטיים).

תוצאת מעניינת נוספת היא משפט מהני, אשר קובע כי אם קיימת שפה דלילה שהיא NP-שלמה אז P=NP.

משפט אדלמן

משפט אדלמן קובע כי המחלקה BPP מוכלת ב-P/Poly.

הוכחה

תהא $L\in BPP$. נוכיח ש $L\in P/poly$. תהא $M$ מכונת טיורינג שמסווגת נכונה קלטים ב$L$ בהסתברות $2/3$ ורצה בזמן פולינומי באורך הקלט לכל היותר. מאחר שזמן הריצה הוא פולינומי לכל היותר, בוודאי שמספר הטלות המטבע של האלגוריתם הוא פולינומי לכל היותר. ידוע שעל ידי הרצת $M$מספר פולינומי לכל היותר של פעמים והכרעה לפי רוב (למשל, אם ביותר מחצי מהרצות המכונה קיבלנו שהמילה כן בשפה, נחזיר כן), ניתן לחסום את הסתברות השגיאה ב$2^{-p(|x|)}$ לכל פולינום $p$ (בעזרת חסם צ'רנוף). בפרט אם נבחר $p(n)=2n$, אז קיימת מכונת טיורינג $M^{*}$ כך ש:

$\Pr[M^{*}\ is\ wrong\ on\ input\ x]\leq 2^{-2|x|}$

נסתכל על מחרוזת הטלות המטבע של $M^{*}$. נקבע מספר טבעי $n$, ונסתכל מעכשיו רק על קלטים באורך $n$. נקרא למחרוזת הטלות "טובה" אם לכל קלט (באורך $n$) המכונה צודקת, ו"רעה" אחרת. נניח שקיימת מחרוזת טובה, ואז היא תהיה מחרוזת העצה של המכונה שנבנה עבור $L$. המכונה תריץ את $M^{*}$ באופן דטרמינסטי: בכל פעם שהמכונה תצטרך להטיל מטבע היא תקרא במקום זה את התו הבא במחרוזת הטובה שלנו ותשתמש בו. בוודאי שזו מכונה הרצה בזמן פולינומי לכל היותר ובעקבות ההערה לעיל על כך שמספר ההטלות הוא פולינומי לכל היותר, אורך העצה הוא פולינומי לכל היותר.

אם כך, נשאר רק להוכיח שקיימת מחרוזת טובה. נעשה זאת בעזרת טיעון הסתברותי. ההסתברות שמחרוזת אקראית תהיה רעה היא:

$\Pr[w\ is\ bad]=\Pr[\exists x\in \{0,1\}^{n}:\ M^{*}\ is\ wrong\ with\ coin\ tosses\ by\ w]\leq \sum _{x\in \{0,1\}^{n}}\Pr[M^{*}(x)\ is\ wrong\ with\ coin\ tosses\ by\ w]\leq \sum _{x\in \{0,1\}^{n}}2^{-2n}=2^{n}2^{-2n}=2^{-n}$

עבור $n\geq 1$, ההסתברות הנ"ל קטנה ממש מ-1, ועל כן לא ייתכן שכל המחרוזות הן מחרוזות רעות, וקיימת מחרוזת טובה.

משפט מהני

משפט מהני קובע כי אם קיימת שפה דלילה שהיא NP שלמה, אז P=NP.

פרק זה לוקה בחסר. אנא תרמו לוויקיפדיה והשלימו אותו. ייתכן שתמצאו פירוט בדף השיחה. כן.

קריפטוגרפיה

למחלקה P/Poly שימושים רבים בקריפטוגרפיה. בקריפטוגרפיה הקלאסית מודל נחשב בטוח אם הוא בטוח נגד יריב PPT. אך על מנת להשיג בטיחות סמנטית חזקה יותר, ניתן להגדיר את היריב שלנו בתור יריב לא אוניפורמי. בחיים האמיתיים יריב לא אוניפורמי הוא יריב אשר יכול לבצע חישובים כבדים מאוד עד לאורך מסוים. אחד השימושים לדוגמה הוא יצירת רדוקציה לא אוניפורמית. כאשר רוצים להוכיח טענה על ידי שימוש במשתנה היברידי, בעזרת הרדוקציה הלא אוניפורמית ניתן לדעת בין איזה איברים קיים הבדל על ידי שליחת האינדקס הקריטי כמחרוזת עצה.

לקריאה נוספת

Arora, Sanjeev; Barak, Boaz (2009), Computational complexity. A modern approach, Cambridge University Press, ISBN 978-0-521-42426-4