שפה דלילה

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

שפה אונארית היא מקרה פרטי של שפה דלילה, בו יש רק מילה אחת בשפה.

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

ערך זה הוא קצרמר בנושא מדעי המחשב. אתם מוזמנים לתרום למכלול ולהרחיב אותו.