בעיית הספיקות

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

בעיית הספיקות בתחשיב הפסוקים (בקיצור: SAT - קיצור של המילה האנגלית Satisfiability, שמשמעה ספיקות) הוא שמה של בעיית הכרעה הנחקרת במסגרת תורת הסיבוכיות במדעי המחשב. בעיה זו הייתה הבעיה הראשונה עליה הוכח כי היא NP-שלמה (הוכחה זו היא משפט קוק-לוין), טענה שמשמעותה שלא נמצא לבעיה זו פתרון אלגוריתמי הרץ בזמן סביר, ומקובל להאמין כי לא קיים אחד. (עוד בנושא זה בערך על המחלקה NP) באמצעות בעיה זו ניתן להוכיח כי בעיות רבות נוספות הן NP-שלמות.

תיאור הבעיה[עריכת קוד מקור | עריכה]

בלוגיקה מתמטית נהוג לומר על נוסחה בתחשיב פסוקים שהיא ספיקה אם קיימת השמה של ערכי אמת עבורה הנוסחה היא אמיתית. למשל, הנוסחה "A או B" היא ספיקה, כי ניתן לקבוע את ערכו של A ל-"אמת" וערך האמת שיתקבל עבור הנוסחה כולה יהיה "אמת" גם הוא. לעומת זאת, הנוסחה "A וגם לא A" אינה ספיקה, כי לא ייתכן כי גם "A" וגם "לא A" יהיו יחד בעלי הערך "אמת".

באופן כללי, בעיית SAT היא הבעיה הבאה: בהינתן נוסחה בתחשיב הפסוקים שמכילה רק קשרים מסוג "גם", "או" ו-"לא", האם קיימת השמה של ערכי אמת למשתנים כך שהנוסחה תקבל ערך אמת?

ניתן להראות שגם אם נגביל את הבעיה לנוסחאות הניתנות בצורה הנורמלית הקוניונקטיבית (CNF), הבעיה תשאר NP-קשה. לכן, בשל נוחות העבודה עם נוסחאות בצורת CNF, מקובל לנסח את הבעיה רק עבור נוסחאות הנתונות בצורה זו (וריאנט זה של הבעיה נקרא לעתים CNF-SAT או CSAT).

לבעיית ה-SAT חשיבות בתחומים רבים של מדעי המחשב, ובהם אלגוריתמיקה, בינה מלאכותית ותכן חומרה.

הגבלת אורך הפסוקיות[עריכת קוד מקור | עריכה]

מקובל להתייחס בשם k\text{-SAT} לבעיית סיפוק נוסחאות בצורת CNF אשר כל הפסוקיות המופיעות בהן מאורך \ k. ניתן לראות כי הבעיות 1\text{-SAT} ו\ 2\text{-SAT} ניתנות לפתרון בזמן פולינומי. (כלומר, שייכות ל-P), בעוד שעבור \ k\ge 3 הבעיה המתקבלת NP-קשה. (כלומר, צמצום הבעיה לפסוקיות מאורך \ k בלבד לא הופך אותה לקלה יותר)

בעזרת למת המקומיות של לובאס ניתן להראות כי אם כל משתנה מופיע בלכל היותר  2^{k}/4k פסוקיות, אזי קיימת השמה מספקת. מאידך, ייתכן כי לא ניתן למצוא את ההשמה המספקת בזמן פולינומי.

בעיות אופטימיזציה נגזרות[עריכת קוד מקור | עריכה]

בהינתן נוסחת CNF בעלת \ m פסוקיות, ניתן לשאול מה מספר הפסוקיות המקסימלי אשר ניתן לספק באמצעות השמת ערכי אמת. (אם הנוסחה ספיקה, מספר זה הוא \ m) בעיה זו מכונה בעיית ספיקות מקסימלית. (באנגלית, Max-Sat) ניתן להוסיף ולהכליל בעיה זו באמצעות קביעת משקל \ w_i לכל פסוקית, ומציאת השמת ערכי אמת עבורה משקל הפסוקיות המסופקות יהיה מקסימלי. גרסה זו של הבעיה נקראת בעיית הספיקות המשוקללת המקסימלית. (באנגלית Max-W-Sat)

נמצאו אלגוריתמי קירוב רבים לבעיות אלה, אשר נותנים קירובים שונים, (1/2‏‏[1], 2/3‏‏[2], 3/4‏‏[3]‏‏[4] ואף יותר מכך), אך הוכח‏‏[5] בשנת 1997 כי לא ייתכן אלגוריתם פולינומי אשר מבטיח פתרון טוב יותר מאשר 7/8-קירוב. (אלא אם כן P=NP) לכן, שייכות הבעיות Max-Sat ו-Max-W-Sat למחלקה APX אך לא ל-PTAS. (אלא אם כן, P=NP, ואז שתי המחלקות הנ"ל שוות)

ראו גם[עריכת קוד מקור | עריכה]

קישורים חיצוניים[עריכת קוד מקור | עריכה]

הערות שוליים[עריכת קוד מקור | עריכה]

  1. ^ D.S. Johnson, Approximation algorithms for combinatorial problems, journal of Computer and System Sciences 9 (1974), pp. 256-278
  2. ^ J. Chen, D. K. Friesen and H. Zheng, Tight bound on the Johnson’s algorithm for Max-SAT, Proc. 12th Annual IEEE Conf. On Computational Complexity (1997), Ulm, Germany, pp. 274-281
  3. ^ M. Yannakakis, On the Approximation of Maximum Satisfiability, Journal of Algorithms 17 (1994), pp. 475-502
  4. ^ M. X. Goemans and D. P. Williamson, New 3/4-approximation algorithms for MAX SAT, SIAM Journal on Discrete Mathematics 7 (1994), pp. 656-666
  5. ^ J. Håstad, Some optimal inapproximability results, Proc. 28th Annual ACM Symp. on Theory of Computing (1997), El Paso, Texas, pp. 1-10
P Computer-science.png ערך זה הוא קצרמר בנושא מדעי המחשב. אתם מוזמנים לתרום לוויקיפדיה ולהרחיב אותו.