P/Poly – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
אין תקציר עריכה |
אין תקציר עריכה |
||
שורה 9:
הגדרה נוספת ל-P/Poly, היא על ידי [[מעגלים בוליאנים]], כלומר שפה L נמצאת ב-P/Poly אם ורק אם קיימת משפחת מעגלים בוליאנים <math>{\{C_n\}}_{n=1}^\infty</math> שמכריעה אותה.
המחלקה [[BPP (מחלקת סיבוכיות)|BPP]], מחלקת הבעיות הפתירות על ידי [[אלגוריתם אקראי]] בעל [[זמן ריצה פולינומי]], אשר צודק בהסתברות שהיא אחד חלקי פולינום כלשהו באורך הקלט, קיימת טכניקה אשר נקראת "הגברה" אשר באמצעותה ניתן להגיע לסיכוי שהוא אחד חלקי אקספוננט באורך הקלט על ידי הרצה חוזרת של המכונה מספר פולינומי של פעמים בגודל הקלט, ובכך לשמור על זמן ריצה פולינומי, למען הפשטות, מניחים שקיים אלגוריתם אשר צודק ב2/3 מהמקרים, ידועה להיות מוכלת ב-P/Poly (משפט אדלמן). זו התוצאה הבסיסית בדרנדומיזציה, תחום החוקר מתי אפשר להפוך אלגוריתמים מאקראיים ל-לא אקראיים.
תוצאת מעניינת נוספת היא משפט מהני, אשר קובע כי אם קיימת שפה דלילה שהיא NP-שלמה אז P=NP.
| |||