בעיית הספיקות – הבדלי גרסאות

אין תקציר עריכה
(←‏הגבלת אורך הפסוקיות: תיקנתי שגיאה)
 
== הגבלת אורך הפסוקיות ==
מקובל להתייחס בשם <math>k\text{-SAT}</math> לבעיית סיפוק נוסחאות בצורת CNF אשר כל הפסוקיות המופיעות בהן מאורך <math>\ k</math>. ניתן לראות כי הבעיות <math>1\text{-SAT}</math> ו<math>\ 2\text{-SAT}</math> ניתנות לפתרון בזמן פולינומי. (כלומר, שייכות ל-[[P (סיבוכיות)|P]]), בעוד שעבור <math>\ k\ge 3</math> הבעיה המתקבלת [[NP (מחלקת סיבוכיות)#בעיות NP-קשות (NP-Hard) ובעיות NP-שלמות (NPC)|{{כ}}NP-קשה.שלמה]] (כלומר, צמצום הבעיה לפסוקיות מאורך <math>\ k</math> בלבד לא הופך אותה לקלה יותר)
 
בעזרת [[למת המקומיות של לובאס]] ניתן להראות כי אם כל משתנה מופיע בלכל היותר <math> 2^{k}/4k</math> פסוקיות, אזי קיימת השמה מספקת. מאידך, ייתכן כי לא ניתן למצוא את ההשמה המספקת בזמן פולינומי.
24

עריכות