שפה דלילה

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

שפה אונארית היא מקרה פרטי של שפה דלילה, בו יש רק מילה אחת בשפה. דוגמה לא טריוויאלית לשפה דלילה היא קבוצת המחרוזות שמכילות בדיוק k אחדות, ל-k קבוע כל שהוא; לכל n, ישנן ${\binom {n}{k}}$ מחרוזות בלבד בשפה, ביטוי החסום על ידי n^k.

קשרים למחלקות סיבוכיות אחרות

SPARSE מכילה את TALLY, מחלקת השפות האונאריות, כיון שהן מכילות לכל היותר מילה אחת מכל אורך. אף על פי שלא כל השפות ב-P/poly הן דלילות, קיימת רדוקציה פולינומית מכל שפה ב-P/poly לשפה דלילה.^[1] כל שפה דלילה נמצאת ב-P/Poly, מכיוון שניתן לבקש שמחרוזת העצה תהיה כל המילים בשפה מאורך n משורשרות אחת לשנייה.

פורצ'ן הראה ב-1979 שאם קיימת שפה דלילה שמשלימתה היא NP-שלמה (co-NP-complete), אז P=NP.^[2] מהניי השתמש בכך כדי להראות ב-1982 שאם שפה דלילה כל שהיא היא NP-שלמה, אז P = NP (משפט מהניי)^[3] הוכחה פשוטה יותר לכך ניתנה ב-1991.^[4] הטיעון של מהניי למעשה לא דורש שהשפה תהיה ב-NP, כך שלמעשה יש שפה דלילה שהיא NP-קשה אם ורק אם P = NP.^[5] מעבר לכך, E ≠ NE אם ורק אם קיימת שפה דלילה ב-NP שאינה ב-P.^[6] קיימת רדוקצית טיורינג (בניגוד לרדוקציית קארפ ממשפט מהניי) משפה NP-שלמה לשפה דלילה אם ורק אם ${\textbf {NP}}\subseteq {\textbf {P}}/{\text{poly}}$ . ב-1999 הוכח שאם קיימת שפה דלילה שהיא P-שלמה, אז L = P.^[7]

הערות שוליים

^ Jin-Yi Cai. Lecture 11: P=poly, Sparse Sets, and Mahaney's Theorem. CS 810: Introduction to Complexity Theory. The University of Wisconsin–Madison. September 18, 2003 (PDF)
^ S. Fortune. A note on sparse complete sets. SIAM Journal on Computing, volume 8, issue 3, pp.431–433. 1979.
^ S. R. Mahaney. Sparse complete sets for NP: Solution of a conjecture by Berman and Hartmanis. Journal of Computer and System Sciences 25:130–143. 1982.
^ M. Ogiwara and O. Watanabe. On polynomial time bounded truth-table reducibility of NP sets to sparse sets. SIAM Journal on Computing volume 20, pp.471–483. 1991.
^ Balcázar, José Luis; Díaz, Josep; Gabarró, Joaquim (1990). Structural Complexity II. Springer. pp. 130–131. ISBN 3-540-52079-1.
^ Juris Hartmanis, Neil Immerman, Vivian Sewelson. Sparse Sets in NP-P: EXPTIME versus NEXPTIME. Information and Control, volume 65, issue 2/3, pp.158–181. 1985. At ACM Digital Library
^ Jin-Yi Cai and D. Sivakumar. Sparse hard sets for P: resolution of a conjecture of Hartmanis. Journal of Computer and System Sciences, volume 58, issue 2, pp.280–296. 1999. ISSN 0022-0000. At Citeseer

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

23315566שפה דלילה

[1] Jin-Yi Cai. Lecture 11: P=poly, Sparse Sets, and Mahaney's Theorem. CS 810: Introduction to Complexity Theory. The University of Wisconsin–Madison. September 18, 2003 (PDF)

[2] S. Fortune. A note on sparse complete sets. SIAM Journal on Computing, volume 8, issue 3, pp.431–433. 1979.

[3] S. R. Mahaney. Sparse complete sets for NP: Solution of a conjecture by Berman and Hartmanis. Journal of Computer and System Sciences 25:130–143. 1982.

[4] M. Ogiwara and O. Watanabe. On polynomial time bounded truth-table reducibility of NP sets to sparse sets. SIAM Journal on Computing volume 20, pp.471–483. 1991.

[5] Balcázar, José Luis; Díaz, Josep; Gabarró, Joaquim (1990). Structural Complexity II. Springer. pp. 130–131. ISBN 3-540-52079-1.

[6] Juris Hartmanis, Neil Immerman, Vivian Sewelson. Sparse Sets in NP-P: EXPTIME versus NEXPTIME. Information and Control, volume 65, issue 2/3, pp.158–181. 1985. At ACM Digital Library

[7] Jin-Yi Cai and D. Sivakumar. Sparse hard sets for P: resolution of a conjecture of Hartmanis. Journal of Computer and System Sciences, volume 58, issue 2, pp.280–296. 1999. ISSN 0022-0000. At Citeseer

[1]

[2]

[3]

[4]

[5]

[6]

[7]

שפה דלילה

קשרים למחלקות סיבוכיות אחרות

הערות שוליים

תפריט ניווט

חיפוש