הצגת המקור של הדף "בעיית הכרעה"

[[קובץ:Decision Problem He.svg|שמאל|150 פיקסלים]]

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

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

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

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

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

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

כל [[קלט]] (סופי) אפשרי הנתון ב[[שפה פורמלית|שפה]] כלשהי ניתן לקודד (לייצג) כ[[מספר טבעי]]. קידוד שכזה נקרא [[מספור גדל]] ומחשבים מודרניים מיישמים אותו על ידי [[בסיס בינארי|קידוד בינארי]].{{הערה|1=קיומו של הקידוד נובע למעשה מהעובדה שקבוצת המילים האפשריות בשפה כלשהי היא [[קבוצה בת-מנייה]].}} בהינתן קידוד שכזה, לכל בעיית הכרעה ניתן להגדיר את הקבוצה <math>A</math> הכוללת את כל המספרים הטבעיים שמקודדים קלטים שלגביהם התשובה לבעיה היא "כן". ולהפך, לכל קבוצה של מספרים טבעיים <math>A</math> ניתן להגדיר בעיית הכרעה שמשיבה "כן" על כל הקלטים המקודדים על ידי מספר טבעי שנמצא ב-<math>A</math>. במילים אחרות, את קבוצת כל בעיות ההכרעה ניתן לזהות עם [[קבוצת חזקה|קבוצת כל התת-קבוצות]] של הטבעיים, <math>\mathcal{P}(\mathbb{N})</math>.

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

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

==סיבוכיות==

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

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

==קישורים חיצוניים==
* {{MathWorld}}
* {{בריטניקה}}
==הערות שוליים==
{{הערות שוליים}}

{{בקרת זהויות}}

[[קטגוריה:בעיות חישוביות]]
[[קטגוריה:חישוביות]]