שפה דלילה

בתורת החישוביות והסיבוכיות, שפה דלילה היא שפה שמכילה "קצת" מילים. באופן פורמלי: שפה L תיקרא דלילה אם קיים פולינום $p(*)$ כך שעבור כל $n\in N$ מספר המילים מאורך n בשפה קטן או שווה ל-$p(n)$. כלומר, $\mathrm{\forall }n\in N,|L\cap \{0,1{\}}^n|\le p(n)$. שפות דלילות משמשות בעיקר לחקר הקשרים בין מחלקת הסיבוכיות NP למחלקות אחרות. מחלקת הסיבוכיות של כל השפות הדלילות מכונה SPARSE. שפה דלילה נקראת כך היות שיש סך הכל 2ⁿ מחרוזות באורך n, ואם שפה מכילה רק מספר פולינומי מהן, אז היחס של מספר המחרוזות באורך n שהיא מכילה שואף במהירות לאפס, ככל ש-n גדל.

שפה אונארית היא מקרה פרטי של שפה דלילה, בו יש רק מילה אחת בשפה. דוגמה לא טריוויאלית לשפה דלילה היא קבוצת המחרוזות שמכילות בדיוק k אחדות, ל-k קבוע כל שהוא; לכל n, ישנן $(\genfrac{}{}{0ex}{}{n}{k})$ מחרוזות בלבד בשפה, ביטוי החסום על ידי 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-שלמה לשפה דלילה אם ורק אם $\mathbf{\text{NP}}\subseteq \mathbf{\text{P}}/\text{poly}$. ב-1999 הוכח שאם קיימת שפה דלילה שהיא P-שלמה, אז L = P.תבנית:הערה