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