בתשובה לשוטה הכפר הגלובלי, 22/09/05 16:28
אפילו יותר מבולבל 332059
מה אם n=1 ?

_____________
ברקת, 3 יחידות מתימטיקה פלוס העתקה בבגרות.
אפילו יותר מבולבל 332125
הא! כבר סיפרו באייל את הבדיחה הזאת. בדיחות שמספרים יותר מפעם אחת, חובה להרוס :)

NP זה שם של אובייקט אחד ולא כפל בין שני אובייקטים. P ו-NP הן מחלקות ולא מספרים. להלן קצרקורס-מזורז-רצח:

הסבר בעיית P=?=NP ב-‏30 שניות (מהזיכרון ועם נסיון להמנע מהגדרות פורמליות):

P היא מחלקת‏1 השפות‏2 המתקבלות‏3 ע"י מכונות טיורינג‏4 דטרמיניסטיות‏5 בזמן פולינומיאלי‏6.

NP היא מחלקת השפות המתקבלות ע"י מכונות טיורינג לא-דטרמיניסטיות‏7 בזמן פולינומיאלי.

ניסוח הבעיה: אנחנו יודעים ש-P מוכלת ב-NP (כל שפה ב-P היא גם ב-NP). אנחנו לא יודעים להראות (או להפריך) ש-NP מוכלת ב-P ולכן איננו יודעים בודאות אם הן שוות או שונות. הרוב סבור שהטענה ש-P=/=NP היא הסבירה מבין שתי האופציות, אבל אף אחד עדיין לא הוכיח או הפריך את אחת משתי האפשרויות.

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

______
1 מחלקה זו מן קבוצה גדולה שכזו.
2 שפה זה אוסף של מילים הכתובות באיזה א"ב סופי.
3 "שפה שמתקבלת ע"י מ"ט M" זה אוסף של מילים כך שעבור כל מילה המכונה M תעצור ותקבל אותה (ז'תומרת המכונה תעצור ותגיד לנו "חביבי, המילה שנתת לי היא בסדר היא").
4 מ"ט זה בסה"כ מן מחשב פרימיטיבסקי שכל מה שיש לו זה אוסף סופי של מצבים וזיכרון (סרט עליו הוא יכול לכתוב ולקרוא).
5 דטרמניסטית משום שבהינתן רגע נתון במהלך החישוב בו "מצב המכונה+האות עליה מביטה המכונה" (בקיצור: קונפיגורציה) בו היא נמצאת - תמיד מוגדר לה מה היא צריכה בדיוק לעשות והיא תמיד עושה בדיוק את זה (במילים אחרות: יש לה פונקציית מעבר דטרמניסטית).
6 ז"א בזמן החסום ע"י פולינום כלשהו. או במילים פשוטות: מהר יחסית (בניגוד לריצה בזמן אקספוננציאלי).
7 מכונה נוירוטית שיכולה "לנחש" במהלך החישוב, בהיותה בקונפיגורציה מסוימת, לאיזה מצב מתחשמק לה לקפץ לפני ביצוע צעד החישוב הבא. מילה מסוימת מתקבלת ע"י מכונה כזאת אם קיימת סידרה *כלשהי* של צעדים/ניחושים שיובילו את המכונה מהמצב ההתחלתי אל המצב המקבל. השפה המתקבלת היא אוסף כל המילים המתקבלות ע"י המכונה הזאת. על פניו נראה כאילו מ"ט כאלה הן הרבה יותר מהירות ממכונות "רגילות" (דטרמניסטיות).
אפילו יותר מבולבל 332126
ב-‏3 צריך להיות "שעבור כל מילה *בשפה*, המכונה M...".
אפילו יותר מבולבל 332210
לדעתי, בקצרקורס-מזורז-רצחים עדיף להשתמש בהגדרה אחרת ל־P ו¯NP (שקולה):‏
P היא קבוצת הבעיות שניתן למצוא להן פתרון ביעילות (בזמן פולינומי).
NP היא קבוצת הבעיות שניתן לוודא ביעילות האם משהו הוא פתרון שלהן או סתם קשקוש.

בהצגה הזאת, כל בר דעת מבין ש־NP הרבה יותר גדולה מ־P, וקולט את התסכול של מדעני המחשב שכבר 40 שנה לא מצליחים להוכיח כזה דבר ברור.
אפילו יותר מבולבל 332244
אכן, גם אני אוהב יותר את הפשטות שבההגדרה הזאת של NP, אם כי אני לא שותף להרגשה שנביעת גודלה של NP מכך זה "כזה דבר ברור" (אם כי אני לא בטוח שבר דעת אנוכי).

אבל אולי כדאי לחזור לנושא הדיון המעניין, לפני ששדמי יצוץ פה ויוכיח ש-NP מוכלת *ממש* ב-P, באמצעות מ"ט בעלת קבוצת מצבים מלאה.
אפילו יותר מבולבל 332317
הערה לגבי ‏1: במקרה הזה "מחלקה" היא באמת קבוצה (שלא כמו "מחלקת כל הקבוצות", למשל). היא אפילו די קטנה. העוצמה שלה היא א_0.
אפילו יותר מבולבל 332344
וואלה.
אפילו יותר מבולבל 332321
פשששששי... אתה מנסה להחזיר לי על הפעם ההיא שניסיתי להסביר לך מה זה פוסט מודרניזם? :-)
אפילו יותר מבולבל 332343
בטח :)

חזרה לעמוד הראשי המאמר המלא

מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים