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

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