שפה דלילה

מתוך המכלול, האנציקלופדיה היהודית
קפיצה לניווט קפיצה לחיפוש

בתורת החישוביות והסיבוכיות, שפה דלילה היא שפה שמכילה "קצת" מילים. באופן פורמלי: שפה L תיקרא דלילה אם קיים פולינום כך שעבור כל מספר המילים מאורך n בשפה קטן או שווה ל-. כלומר, .

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

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

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