למחלקה P/Poly שימושים רבים בקריפטוגרפיה. בקריפטוגרפיה הקלאסית מודל נחשב בטוח אם הוא בטוח נגד יריב PPT. אך על מנת להשיג בטיחות סמנטית חזקה יותר, ניתן להגדיר את היריב שלנו בתור יריב לא אוניפורמי. בחיים האמיתיים יריב לא אוניפורמי הוא יריב אשר יכול לבצע חישובים כבדים מאוד עד לאורך מסוים.
אחד השימושים לדוגמה הוא יצירת רדוקציה לא אוניפורמית. כאשר רוצים להוכיח טענה על ידי שימוש במשתנה היברידי, בעזרת הרדוקציה הלא אוניפורמית ניתן לדעת בין איזה איברים קיים הבדל על ידי שליחת האינדקס הקריטי כמחרוזת עצה.
לקריאה נוספת.
Arora, Sanjeev; Barak, Boaz (2009), Computational complexity. A modern approach, Cambridge University Press,
שפה דלילה
בתורת החישוביות והסיבוכיות, שפה דלילה היא שפה שמכילה "קצת" מילים. באופן פורמלי: שפה L תיקרא דלילה אם קיים פולינום formula_1 כך שעבור כל formula_2 מספר המילים מאורך n בשפה קטן או שווה ל-formula_3. כלומר, formula_4. שפות דלילות משמשות בעיקר לחקר הקשרים בין מחלקת הסיבוכיות NP למחלקות אחרות. מחלקת הסיבוכיות של כל השפות הדלילות מכונה SPARSE.
שפה דלילה נקראת כך היות שיש סך הכל 2"n" מחרוזות באורך n, ואם שפה מכילה רק מספר פולינומי מהן, אז היחס של מספר המחרוזות באורך n שהיא מכילה שואף במהירות לאפס, ככל ש-n גדל.
שפה אונארית היא מקרה פרטי של שפה דלילה, בו יש רק מילה אחת בשפה.
דוגמה לא טריוויאלית לשפה דלילה היא קבוצת המחרוזות שמכילות בדיוק k אחדות, ל-k קבוע כל שהוא; לכל n, ישנן formula_5 מחרוזות בלבד בשפה, ביטוי החסום על ידי "n""k".
קשרים למחלקות סיבוכיות אחרות.
SPARSE מכילה את TALLY, מחלקת השפות האונאריות, כיון שהן מכילות לכל היותר מילה אחת מכל אורך. אף על פי שלא כל השפות ב-P/poly הן דלילות, קיימת רדוקציה פולינומית מכל שפה ב-P/poly לשפה דלילה.
כל שפה דלילה נמצאת ב-P/Poly, מכיוון שניתן לבקש שמחרוזת העצה תהיה כל המילים בשפה מאורך n משורשרות אחת לשנייה.
פורצ'ן הראה ב-1979 שאם קיימת שפה דלילה שמשלימתה היא NP-שלמה (co-NP-complete), אז P=NP.
מהניי השתמש בכך כדי להראות ב-1982 שאם שפה דלילה כל שהיא היא NP-שלמה, אז P = NP (משפט מהניי)
הוכחה פשוטה יותר לכך ניתנה ב-1991.
הטיעון של מהניי למעשה לא דורש שהשפה תהיה ב-NP, כך שלמעשה יש שפה דלילה שהיא NP-קשה אם ורק אם P = NP.
מעבר לכך, E ≠ NE אם ורק אם קיימת שפה דלילה ב-NP שאינה ב-P.
קיימת רדוקצית טיורינג (בניגוד לרדוקציית קארפ ממשפט מהניי) משפה NP-שלמה לשפה דלילה אם ורק אם formula_6.
ב-1999 הוכח שאם קיימת שפה דלילה שהיא P-שלמה, אז L = P.
שפה אונארית
שפה אונארית היא שפה שמכילה רק מילים מהצורה formula_1, כלומר שפה L תיקרא אונארית אם formula_2, כאשר 1 יכול להיות כל תו בא"ב סופי. (למרות שמקובל לדבר על א"ב של 0 ו-1 בלבד).
לדוגמה: השפה של כל המחרוזות שמייצגות את המספרים formula_3 הראשוניים מעל א"ב של {0,1} היא שפה אונארית.
לכל שפה ניתן להגדיר שפה אונארית מקבילה, כאשר פשוט "מותחים" כל מילה לייצוג אונארי. דוגמה: המילה 1001 (9 בבינארית) תימתח למילה 111111111 (9 פעמים 1).
שפה שניתנת להכרעה בזמן אקספוננציאלי, המקבילה האונרית שלה ניתן להכרעה בזמן ליניארי, אך שפה שאינה כריעה בגרסה הרגילה שלה, אינה כריעה גם בגרסה האונארית. כל שפה אונארית נמצאת ב-P/Poly, כולל שפות אונאריות לא כריעות.
בית קדרות
בית קַדְרוּת (באנגלית: Bleak House) הוא רומן מאת צ'ארלס דיקנס שפורסם לראשונה בהמשכים ממרץ 1852 עד ספטמבר 1853. ברומן מספר רב של דמויות וכמה עלילות משנה. הסיפור מסופר לסירוגין בגוף ראשון על ידי גיבורת הרומן, אסתר סאמרסון, ועל ידי מספר יודע כל. במרכז הרומן מגוללת פרשה של תביעה משפטית, ג'ארנדייס וג'ארנדייס, שנוצרה בעקבות כתיבת מספר צוואות סותרות. פרשה משפטית זו מהווה בסיס לביקורת שמטיח דיקנס במערכת המשפט הבריטית. בנוסף הוא משתמש בחוויותיו מתקופת עבודתו כמזכיר משפטי, ומניסיונו באכיפת חוקי זכויות יוצרים על ספריו.
על אף שבין אנשי מערכת המשפט היו שטענו שהסאטירה של דיקנס מוגזמת, חיזק הרומן את דרישתם של קבוצת משפטנים לערוך שינויים במערכת המשפט, ששיאה היה בחוקי הרפורמה המשפטית שהתקבלו בשנות השבעים של המאה התשע עשרה.
יש חילוקי דעות בין חוקרים לגבי זמן התרחשות העלילה. היסטוריון המשפט האנגלי סר ויליאם הולדסוורת' טוען שהשנה היא 1827, אולם ההתייחסות לבניית מסילה בפרק 55 מרמזת על שנות השלושים של המאה התשע העשרה.
תקציר עלילה.
סר לסטר דדלוק ואשתו ליידי הונוריה חיים באחוזה כפרית בשם צ'סני וולד. סר לסטר אינו מודע לכך שלאשתו היה רומן לפני הנישואים עם קפטן הודון, והיא ילדה לו בת. ליידי דדלוק חושבת שבתה מתה.
הבת, אסתר סאמרסון, למעשה נשארה בחיים וגדלה אצל מיס ברברי, אחותה של ליידי דדלוק. אסתר לא יודעת שמיס ברברי היא דודתה. אחרי מותה של מיס ברברי, מתמנה ג'ון ג'אנדרייס לאפוטרופוס של אסתר, ומעביר את הטיפול בחינוכה לעורך הדין קנג'. אחרי שלמדה בבית ספר במשך שש שנים, עוברת אסתר לחיות בביתו של מר ג'אנדרייס "בית קדרות".
במקביל מקבל ג'ון גארנדייס משמורת על שני צעירים אחרים, ריצ'רד קרסטון ואדה קלייר (דודנים של אסתר). הם יורשים באחת הצוואות בתיק ג'ארנדייס וג'ארנדייס. גם האפוטרופוס שלהם הוא מוטב בצוואה אחרת בתיק, ושתי הצוואות סותרות זו את זו. עד מהרה ריצ'רד ואדה מתאהבים, גם אם מר ג'ארנדייס אינו מתנגד לשידוך ביניהם, הוא מתנה זאת בכך שריצ'רד יבחר לעצמו מקצוע. בהתחלה ריצ'רד מנסה את תחום הרפואה, ובבית של המורה שלו פוגשת אסתר את הרופא הצעיר מר אלן וודקורט. כשריצ'רד מדבר על הסיכוי להרוויח בתיק ג'ארנדייס וג'ארנדייס מתחנן אליו ג'ון ג'ארנדייס שלא ישים מבטחו במה שהוא מכנה "הקללה המשפחתית".
ליידי דדלוק אף היא יורשת באחת הצוואות של ג'ארנדייס וג'ארנדייס. כשהיא מתבקשת על ידי עורך הדין של המשפחה, מר טולקינגהורן, לחתום על עותק של אחד התצהירים עבור המשפט, היא מזהה את כתב היד של מעתיק המסמך. הדבר מזעזע אותה והיא כמעט מתעלפת, טולקינגהורן שמבחין בדבר פותח בחקירה. הוא מתחקה אחרי המעתיק, ומתברר שזהו עני מרוד העונה לשם "נמו". נמו נפטר לאחרונה, והיחיד שמזהה אותו הוא מטאטא רחובות, נער עני חסר בית בשם ג'ו, שמתגורר במקום הנקרא "טום-לבד-לגמרי" (Tom-All-Alone).
גם ליידי דדלוק חוקרת, ומסווה את עצמה בדמותה של המשרתת האישית שלה, הורטנז. היא משלמת לנער ג'ו כדי שיראה לה את מקום קבורתו של נמו. טולקינגהורן חושד בליידי דדלוק וחושש שהסוד שלה יכול לאיים על שמו הטוב של בעלה סר לסטר. הוא משגיח עליה, ומגייס את המשרתת שלה כדי שתרגל אחריה. הוא גם שוכר את שרותיו של המפקח באקט כדי לסלק את ג'ו מהעיר, שדבר לא יקשר בין נמו לבני משפחת דדלוק.
אסתר פוגשת את ליידי דדלוק בכנסייה, ואחר כך מדברת אתה בצ'סני וולד – אבל אף אחת מהן לא מזהה את הקשר ביניהן. מאוחר יותר ליידי דדלוק מגלה שאסתר היא בתה. אסתר מטפלת בג'ו חסר הבית ונדבקת במחלה (כנראה אבעבועות שחורות) שגורמת להשחתת פניה לצמיתות. ליידי דדלוק מחכה שתבריא ואחר כך מספרת לה את האמת. על אף שאסתר וליידי דדלוק מאושרות להיות יחד, ליידי דדלוק אומרת לאסתר שאסור להן להיפגש ולהודות בקשר שביניהן.
אחרי שאסתר מחלימה היא מגלה שריצ'רד, אחרי שנכשל במקצועות אחדים אותם ניסה, המרה את פיו של האפוטרופוס שלו ומנסה לקדם את "ג'ארנדייס וג'ארנדייס" לטובתו ולטובת אדה. תוך כדי הפסד כל כספו והתדרדרות במצב בריאותו. הוא ואדה מתחתנים והיא נכנסת להריון. גם לאסתר יש פרשת אהבים משלה, מר וודקורט חוזר לאנגליה אחרי שניצל מספינה טרופה, והוא מבקש להיות בחברתה אף על פי שפניה הושחתו בגלל המחלה. למרבה הצער אסתר כבר הבטיחה את ידה לג'ון ג'ארנדייס, האפוטרופוס שלה.
הורטנז וטולקינגהורן מגלים את האמת על עברה של ליידי דדלוק. אחרי שהיא מתעמתת עם טולקינגהורן בורחת ליידי דדלוק מהבית, ומשאירה אחריה פתק התנצלות על התנהגותה. טולקינגהורן מפטר את הורטנז שאינה מועילה לו יותר. הורטנז שמרגישה נבגדת ונטושה, רוצחת את טולקינגהורן ומנסה להטיל את האשמה על ליידי דדלוק. סר לסטר ששומע על מותו של טולקינגהורן ובריחתה של אשתו, סובל משבץ חמור. בכל זאת הוא מצליח להגיד שהוא סולח לאשתו ורוצה שהיא תחזור לביתם.
המפקח באקט, שכבר חקר בעבר מספר עניינים בנוגע ל"ג'ארנדייס וג'ארנדייס" מקבל את המשימה שמטיל עליו סר דדלוק, למצוא את ליידי דדלוק. בתחילה הוא חושד שליידי דדלוק היא הרוצחת, אבל הוא מטהר אותה מכל חשד, אחרי שגילה את אשמתה של הורטנז. באקט מבקש מאסתר לעזור לו למצוא את אמה. ליידי דדלוק שאינה יודעת על סליחתו של בעלה ועל כך שנוקתה מחשד, ממשיכה לשוטט בדרכים הכפריות במזג אוויר קר, לבסוף היא מגיעה לבית הקברות בו קבור אהובה לשעבר, קפטן הודון (נמו) ומתה שם. אסתר ובאקט מוצאים אותה אחרי מותה.