בעיית הכרעה
ויקיפדיה האנציקלופדיה encyclopedia
במתמטיקה ובמדעי המחשב, בעיית הכרעה היא בעיה אשר יש לה תשובה של "כן" או "לא".
דוגמה: השאלה האם מספר טבעי נתון הוא ראשוני היא בעיית הכרעה. מאידך, הבעיה "מציאת המספר הראשוני הקטן ביותר בעל 77 ספרות" אינה בעיית הכרעה, שכן התשובה עבורה אינה "כן" או "לא".
בעיית הכרעה ידועה בתולדות המתמטיקה היא הבעיה העשירית של הילברט.
בעיות הכרעה שקולות לשפות פורמאליות, כך שמילה נתונה נמצאת בשפה אם ורק אם התשובה עבורה בבעיית ההכרעה היא "כן".
קבוצות מסוימות של בעיות הכרעה, כגון זו הקרויה NP-קשה, הן נושא מרכזי במדעי המחשב, בהיותן בגדר בעיה פתוחה רחבת היקף.