בעיית הכרעה ידועה בתולדות המתמטיקה היא הבעיה העשירית של הילברט.
בעיות הכרעה שקולות לשפות, כך שמילה נתונה נמצאת בשפה אם ורק אם התשובה עבורה בבעיית ההכרעה היא "כן".
קבוצות מסוימות של בעיות הכרעה, כגון זו הקרויה NP-קשה, הן נושא מרכזי במדעי המחשב, בהיותן בגדר בעיה פתוחה רחבת היקף.
חישוביות.
תורת החישוביות היא תחום יסודי במדעי המחשב החוקר את היכולות והמגבלות של כל המחשבים באשר הם. שאלה מרכזית בתורת החישוביות היא האם כל בעיית הכרעה ניתנת לפתרון על ידי תוכנית מחשב כלשהי. בהסתמך על משפט קנטור ניתן להראות שהתשובה שלילית.
כל קלט (סופי) אפשרי הנתון בשפה כלשהי ניתן לקודד (לייצג) כמספר טבעי. קידוד שכזה נקרא מספור גדל ומחשבים מודרניים מיישמים אותו על ידי קידוד בינארי. בהינתן קידוד שכזה, לכל בעיית הכרעה ניתן להגדיר את הקבוצה formula_1 הכוללת את כל המספרים הטבעיים שמקודדים קלטים שלגביהם התשובה לבעיה היא "כן". ולהפך, לכל קבוצה של מספרים טבעיים formula_1 ניתן להגדיר בעיית הכרעה שמשיבה "כן" על כל הקלטים המקודדים על ידי מספר טבעי שנמצא ב-formula_1. במילים אחרות, את קבוצת כל בעיות ההכרעה ניתן לזהות עם קבוצת כל התת-קבוצות של הטבעיים, formula_4.
מצד שני, כל תוכנית מחשב היא רצף סופי של סימנים של שפת תכנות. לכן כל תוכנית מחשב ניתן לקודד כמספר טבעי יחיד (ואכן בפועל כל תוכנית מחשב בשפה מסוימת מתרגמת לקידוד בינארי שונה בשפת מכונה). מכאן שקבוצת כל תוכניות המחשב שקולה לקבוצת המספרים הטבעיים formula_5.
משפט קנטור קובע שעוצמת formula_4 (שהיא עוצמת הרצף) גדולה מעוצמת formula_7 (שהיא אָלֶף אֶפֶס), ולכן יש "הרבה יותר" בעיות הכרעה מאשר תוכניות מחשב אפשריות (על אף שמן השניים יש אינסוף). מכאן שישנן בעיות הכרעה (ולמעשה, כמעט כל בעיות ההכרעה) שאינן ניתנות לפתרון על ידי אף תוכנית מחשב. הדוגמה המוכרת ביותר לבעיית הכרעה שאין תוכנית הפותרת אותה היא בעיית העצירה. אלן טיורינג הוכיח זאת בשנת 1936 בשיטת הלכסון. דוגמאות רבות נוספות מגיעות ממשפט רייס.
סיבוכיות.
חלק ניכר מתורת הסיבוכיות עוסק בבעיות הכרעה. העניין בבעיות הכרעה נובע מכך שהטיפול המתמטי בהן הוא פשוט, שכן התשובה לבעיה מוגבלת ל-"כן" ו-"לא". עם זאת, בעיות שאינן בעיות הכרעה ניתנות להמרה לבעיות הכרעה שקולות.
דוגמה לכך היא הבעיה "האם יש גורם ראשוני": כאשר נתונים שני מספרים שלמים, n ו-k, ענה האם ל-n יש גורם ראשוני קטן מ-k. אם אנו מסוגלים לפתור את בעיית ההכרעה הזו באמצעות משאבים בסדר גודל מסוים, אנו יכולים לפתור את הבעיה "פירוק לגורמים", שאינה בעיית הכרעה, באמצעות משאבים מאותו סדר גודל, וזאת על ידי סדרה של שאלות התוחמות את ערכו האפשרי של k.
זמן ריצה לינארי
בתורת הסיבוכיות, המחלקה co-NP היא המחלקה המשלימה למחלקה NP; כלומר, מחלקה שאיבריה הן בעיות המשלימות לבעיות הנמצאות במחלקה NP.
במילים אחרות: בעוד המחלקה NP מכילה בעיות שניתן לבדוק אישור שלהן בזמן פולינומי, המחלקה co-NP מכילה בעיות שניתן לבדוק שלילה שלהן בזמן פולינומי.
לדוגמה: בעיית סכום תת-קבוצה היא בעיית NP. הגדרתה היא: נתונה קבוצה סופית של מספרים שלמים. האם קיימת לקבוצה זו תת-קבוצה, כך שסכום כל איבריה הוא אפס? תשובה מאשרת כלשהי לשאלה זו היא רשימת איברים שתומכים בטענה (סכומם אפס). תשובה זו ניתנת לבדיקה בזמן פולינומי – סכימת האיברים והשוואת הסכום לאפס.
בעיית ה־co-NP המשלימה לה היא: נתונה קבוצה סופית של מספרים שלמים. האם סכום איברי כל תת-קבוצה שונה מאפס? תשובה שוללת לשאלה זו היא רשימת איברים השוללים את הטענה (סכומם אפס). גם דבר זה בדיק בזמן פולינומי – סכימת האיברים והשוואת הסכום לאפס.
המחלקה P היא תת-קבוצה הן של NP והן של co-NP. ההנחה המקובלת היא כי מדובר בהכלה ממש בשני המקרים, וכן כי המחלקות NP ו־co-NP אינן שוות. אם זה אכן כך, אף בעיה NP-שלמה אינה נמצאת ב-co-NP, ואף בעיה co-NP-שלמה אינה נמצאת ב־NP.
ניתן להראות את נכונות הטענה בצורה הבאה - נניח בשלילה כי קיימת בעיה NP-שלמה אשר שייכת ל־co-NP. כיוון שלכל הבעיות במחלקה NP קיימת רדוקציה פולינומית אל הבעיה ה־NP-שלמה, הרי שלכל בעיה ב־NP ניתן לבנות מכונה טיורינג אי-דטרמיניסטית אשר מכריעה את הבעיה המשלימה בזמן פולינומי, כלומר NP היא תת-קבוצה של co-NP. מכאן נובע כי קבוצת הבעיות המשלימות לבעיות ב־NP היא תת-קבוצה של קבוצת הבעיות המשלימות לבעיות ב־co-NP, כלומר co-NP היא תת-קבוצה ב־NP. מכאן נובע ש־NP ו־co-NP הן אותה הקבוצה, בסתירה להנחה המקובלת שהן שונות. באופן דומה ניתן להראות את הטענה השנייה (אף בעיה co-NP-שלמה לא נמצאת ב־NP).
אי לכך, אם ניתן להראות שבעיה מסוימת שייכת הן ל־NP והן ל־co-NP, הרי שמקובל להניח כי זוהי ראיה לכך שבעיה זו אינה NP-שלמה. כך למשל, לגבי בעיית הראשוניות - האם מספר נתון הוא ראשוני - קל לראות שהבעיה ב־co-NP. ההוכחה שמספר אינו ראשוני הוא פשוט מספר אחר שונה מאחד שמחלק אותו. ב-1975 הראה וון פרט כי הבעיה היא ב־NP, ולכן שיערו מאז שהבעיה אינה NP-שלמה. (כיום כבר ידוע שבעיית הראשוניות היא במחלקה P .)
דוגמה נוספת ויותר מעניינת היא בעיית הפירוק לגורמים: בהינתן שני מספרים טבעיים n, k - האם קיים מספר קטן או שווה ל־k אשר מחלק את n? קל לראות שהבעיה ב-NP, ומכיוון שניתן לבדוק האם מספר הוא ראשוני בסיבוכיות זמן פולינומית - נובע שהבעיה היא גם ב-co-NP, בעיית הפירוק לגורמים מפורסמת בכך שעל הקושי של פתירתה מסתמך פרוטוקול ההצפנה RSA (כלומר, אם בעיית הפירוק לגורמים היא ב-P אזי פרוטוקול RSA לא בטוח לשימוש), עם זאת, סביר להניח כי הבעיה הנ"ל היא לא NP-שלמה שכן היא נמצאת גם ב-NP וגם ב-co-NP.
מחלק
במתמטיקה, מספר שלם a הוא מחלק (או גורם) של מספר שלם b אם אפשר לכתוב את b כמכפלה של a במספר שלם אחר. במקרה כזה, השארית בחלוקה של b ב-a היא 0. דוגמה: 5 הוא מחלק של המספר 35, אך לא של המספר 33.
נהוג לסמן את התכונה כך: a|b פירושו "a מחלק את b."
היחס "לחלק את" הוא רפלקסיבי (a|a לכל a), וטרנזיטיבי (אם a|b וגם b|c אז a|c), ולכן הוא מהווה קדם סדר. לעומת זאת היחס אינו אנטי סימטרי (formula_1 מחלקים זה את זה). בין המספרים הטבעיים היחס הוא יחס סדר חלקי.
למושג המחלק המשותף המקסימלי של שני מספרים יש חשיבות רבה בתורת המספרים האלמנטרית.
המשפט היסודי של האריתמטיקה, לפיו כל מספר טבעי יכול להיכתב כמכפלה ייחודית של מספרים ראשוניים, פרט לשינוי הסדר של הגורמים, גורם לעניין מוגבר במספרים הראשוניים המחלקים מספר נתון, כלומר בגורמים הראשוניים שלו.
הכללה.
כאשר עוסקים בחוג כלשהו, גם כן ניתן לדבר על יחס של חלוקה. נאמר כי איבר formula_2 הוא מחלק של איבר formula_3 אם קיים בחוג איבר formula_4 כך ש-formula_5. למשל בחוג הפולינומים במקדמים שלמים, הפולינום formula_6 מחלק את formula_7, כי formula_8.
מושג המחלק נחוץ לצורך עיסוק בתחומי פריקות יחידה.
מספר המחלקים של מספר שלם.
משפט: מספר המחלקים של מספר שלם המיוצג בצורה:
כאשר המספרים:
formula_9
ראשוניים, והמספרים:
formula_10 שלמים,
(על פי המשפט היסודי של האריתמטיקה, לכל מספר שלם יש הצגה יחידה כמכפלה של מספרים ראשוניים),
הוא:
מכאן, פונקציית המחלקים formula_11 הסופרת את המחלקים של formula_12, היא פונקציה כפלית.
לדוגמה ניקח את המספר 12.
ברור כי למספר 12 יש בדיוק שישה מחלקים: 1,2,3,4,6,12
נציג את המספר כמכפלה של ראשוניים:
formula_13, על פי המשפט נובע כי למספר 12 יש בדיוק:
formula_14
מחלקים.
הוכחה:
כדי להיווכח בנכונות המשפט די לשים לב לכך שכל מחלק של המספר
formula_15
הוא מהצורה
formula_16 כאשר formula_17.
כלומר, לכל וקטור מהצורה formula_18 עם formula_17 מותאם מחלק
אחד ויחיד. מקומבינטוריקה בסיסית מקבלים כי מספר הווקטורים הזה הוא בדיוק formula_20, שכן יש לנו formula_21 בחירות אפשריות לקואורדינטה הראשונה, formula_22 בחירות לקואורדינטה השנייה וכן הלאה.
פיגמליון
פיגמליון הוא דמות מן המיתולוגיה של פיניקיה ויוון:
דמות האישה שיצר נראתה כאילו היא חיה ונושמת. פיגמליון התייחס לדמות כאל נסיכה, הלביש אותה, העניק לה מתנות ואף הושיב אותה על ספה יקרת ערך.
בעת הילולת אפרודיטה, לאחר שקיים את כל גינוני הטקס הנדרשים, התפלל פיגמליון לפני המזבח וביקש כי דמות פסל השנהב תינתן לו לאישה. אפרודיטה שמעה את תפילתו ונענתה לה. כששב פיגמליון לביתו ונשק לפסל נדהם לגלות כי היא פוקחת את עיניה ומתעוררת לחיים. אפרודיטה נתנה את ברכתה לנישואיהם של פיגמליון וגלתיאה. בנם שנולד נקרא פאפוס, ועל שמו נקראת העיר פאפוס, המקודשת לאלת האהבה והיופי, אפרודיטה.
הסופר והמחזאי ג'ורג' ברנרד שו התבסס על סיפור זה כאשר כתב את המחזה "פיגמליון" בשנת 1913 (לאחר מכן עובד המחזה למחזמר ולסרט "גבירתי הנאווה").
סיפורם של פיגמליון וגלתיאה משמש עד היום כמשל לנבואה המגשימה את עצמה.
Internet Message Access Protocol
Internet Message Access Protocol (בראשי תיבות: IMAP) הוא פרוטוקול אינטרנט לגישה לדואר אלקטרוני שנמצא על שרת מרוחק ממחשב מקומי.
IMAP הוא אחד משני הפרוטוקולים הנפוצים לקבלת דואר אלקטרוני, ומהווה אלטרנטיבה מתקדמת לפרוטוקול POP3. בעוד פרוטוקול POP3 מאפשר למשתמש לעבוד עם תיבת דואר אחת בלבד, היתרון בפרוטוקול IMAP הוא באפשרות עבודה עם מספר תיבות דואר. בנוסף לכך, IMAP מאפשר עבודה יעילה יותר על ידי קריאת חלקים בודדים מתקן ה-MIME.