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

בעיית הספיקוּת בתחשיב הפסוקים (בקיצור: 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\geq 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, ואז שתי המחלקות הנ"ל שוות)

ראו גם

חיפוש מקומי

קישורים חיצוניים

אלגוריתמים מקורבים לפתרון בעיית הספיקות המרבית

הערות שוליים

^ D.S. Johnson, Approximation algorithms for combinatorial problems, journal of Computer and System Sciences 9 (1974), pp. 256-278
^ 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
^ M. Yannakakis, On the Approximation of Maximum Satisfiability, Journal of Algorithms 17 (1994), pp. 475-502
^ 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
^ J. Håstad, Some optimal inapproximability results, Proc. 28th Annual ACM Symp. on Theory of Computing (1997), El Paso, Texas, pp. 1-10

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

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

[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

[1]

[2]

[3]

[4]

[5]

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

תוכן עניינים

תיאור הבעיה

הגבלת אורך הפסוקיות

בעיות אופטימיזציה נגזרות

ראו גם

קישורים חיצוניים

הערות שוליים

תפריט ניווט

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

תיאור הבעיה

הגבלת אורך הפסוקיות

בעיות אופטימיזציה נגזרות

ראו גם

קישורים חיצוניים

הערות שוליים

תפריט ניווט

חיפוש