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