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.

הוכחה

נראה עבור שפה בBPP שהיא מוכלת ב P/Poly.

תהא $L\in BPP$ ותהא M מכונת טיורינג המכריעה את M על ידי שימוש ב$p(|x|)$ זמן לכל x עבור פולינום $p(\cdot )$ כלשהו. מכיוון שזמן הריצה של M חסום על ידי $p(\cdot )$, גם מספר הטלות המטבע ש-M מבצעת חסום על ידי $p(\cdot )$ . בנוסף, מכיוון ש-L נמצא ב-BPP, לפחות 2/3 מהטלות המטבע האפשריות מוביל לתוצאת אמת. על ידי הפעלת המכונה M מספר k פעמים, הסתברות הטעות היא $2^{-ck}$. נבחר k עבורו מתקיים $ck>2|x|$. כעת מתקיים התנאי הבא: $\forall x\in L,Pr[M(x)=0]\leq 1-2^{-2|x|}$ ולהפך. ידוע לנו שיש בדיוק $2^{|x|}$ קלטים אפשריים, ולכן על פי עקרון שובך היונים קיימת מחרוזת עצה באורך $k*p(|x|)$ אשר עבורה לכל x המכונה M תחזיר תשובה נכונה.

משפט מהני

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

פרק זה לוקה בחסר. אנא תרמו למכלול והשלימו אותו. הסיבה היא: כן.

קריפטוגרפיה

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

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

P/Poly21456175