בעיית הכרעה

במתמטיקה ובמדעי המחשב, בעיית הכרעה היא בעיה אשר יש לה תשובה של "כן" או "לא".

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

בעיית הכרעה ידועה בתולדות המתמטיקה היא הבעיה העשירית של הילברט.

בעיות הכרעה שקולות לשפות פורמאליות, כך שמילה נתונה נמצאת בשפה אם ורק אם התשובה עבורה בבעיית ההכרעה היא "כן".

קבוצות מסוימות של בעיות הכרעה, כגון זו הקרויה NP-קשה, הן נושא מרכזי במדעי המחשב, בהיותן בגדר בעיה פתוחה רחבת היקף.

חישוביות

תורת החישוביות היא תחום יסודי במדעי המחשב החוקר את היכולות והמגבלות של כל המחשבים באשר הם. שאלה מרכזית בתורת החישוביות היא האם כל בעיית הכרעה ניתנת לפתרון על ידי תוכנית מחשב כלשהי. בהסתמך על משפט קנטור ניתן להראות שהתשובה שלילית.

כל קלט (סופי) אפשרי הנתון בשפה כלשהי ניתן לקודד (לייצג) כמספר טבעי. קידוד שכזה נקרא מספור גדל ומחשבים מודרניים מיישמים אותו על ידי קידוד בינארי. בהינתן קידוד שכזה, לכל בעיית הכרעה ניתן להגדיר את הקבוצה $A$ הכוללת את כל המספרים הטבעיים שמקודדים קלטים שלגביהם התשובה לבעיה היא "כן". ולהפך, לכל קבוצה של מספרים טבעיים $A$ ניתן להגדיר בעיית הכרעה שמשיבה "כן" על כל הקלטים המקודדים על ידי מספר טבעי שנמצא ב-$A$. במילים אחרות, את קבוצת כל בעיות ההכרעה ניתן לזהות עם קבוצת כל התת-קבוצות של הטבעיים, ${\mathcal {P}}(\mathbb {N} )$.

מצד שני, כל תוכנית מחשב היא רצף סופי של סימנים של שפת תכנות. לכן כל תוכנית מחשב ניתן לקודד כמספר טבעי יחיד (ואכן בפועל כל תוכנית מחשב בשפה מסוימת מתרגמת לקידוד בינארי שונה בשפת מכונה). מכאן שקבוצת כל תוכניות המחשב שקולה לקבוצת המספרים הטבעיים $\mathbb {N}$.

משפט קנטור קובע שעוצמת ${\mathcal {P}}(\mathbb {N} )$ (שהיא עוצמת הרצף) גדולה מעוצמת $\mathbb {N}$ (שהיא אָלֶף אֶפֶס), ולכן יש "הרבה יותר" בעיות הכרעה מאשר תוכניות מחשב אפשריות (על אף שמן השניים יש אינסוף). מכאן שישנן בעיות הכרעה (ולמעשה, כמעט כל בעיות ההכרעה) שאינן ניתנות לפתרון על ידי אף תוכנית מחשב. הדוגמה המוכרת ביותר לבעיית הכרעה שאין תוכנית הפותרת אותה היא בעיית העצירה. אלן טיורינג הוכיח זאת בשנת 1936 בשיטת הלכסון. דוגמאות רבות נוספות מגיעות ממשפט רייס.

סיבוכיות

חלק ניכר מתורת הסיבוכיות עוסק בבעיות הכרעה. העניין בבעיות הכרעה נובע מכך שהטיפול המתמטי בהן הוא פשוט, שכן התשובה לבעיה מוגבלת ל-"כן" ו-"לא". עם זאת, בעיות שאינן בעיות הכרעה ניתנות להמרה לבעיות הכרעה שקולות.

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

קישורים חיצוניים

• בעיית הכרעה, באתר MathWorld (באנגלית)
• בעיית הכרעה, באתר אנציקלופדיה בריטניקה (באנגלית)