לכסון (שיטת הוכחה) – הבדלי גרסאות

תוכן שנמחק תוכן שנוסף
Egoz1 (שיחה | תרומות)
אין תקציר עריכה
Yonidebot (שיחה | תרומות)
מ בוט החלפות: דוגמה; מסוים; לעתים;
שורה 11:
כבר בראשית בתפתחותם של [[מדעי המחשב]], הבינו ראשי תחום זה כי בנוסף לעבודת המחקר של מציאת [[אלגוריתם|אלגוריתמים]] יעילים לבעיות ספציפיות, יש גם לאפיין את היכולת, או המסוגלות, של מכונות חישוב לפתור בעיות. שאלות אלה הן בעיקר השאלה מה [[מחשב]] (כל מחשב) מסוגל לחשב, ומה לא (במילים אחרות, האם קיימות [[פונקציה|פונקציות]] שלא ניתנות לחישוב, וכיצד ניתן להוכיח זאת), וכן השאלה מהן הבעיות שלא ניתן לחשב בזמן סביר. שאלות אלה מטופלות בתחומי המחקר [[חישוביות]] ו[[סיבוכיות]].<br />
תוך כדי עיסוק במחקר זה, נוצר הצורך למצוא שיטת [[הוכחה]] שבה ניתן יהיה להוכיח כי קיימת בעיה כלשהי לא ניתנת לחישוב, או לחישוב בזמן סביר.<br />
הקושי בטיפול בשאלות מעין אלה הוא ברור: קל מאוד להראות שניתן לפתור בעיה מסויימתמסוימת - וזאת על ידי הצגת [[אלגוריתם]] שפותר את הבעיה. אבל כיצד ניתן להוכיח שלא ניתן לפתור בעיה כלשהי? כיצד ניתן להוכיח שבכלל קיימת בעיה כזו?<br />
==שיטת ההוכחה==
הרעיון הכללי של השיטה הוא גם הרעיון שעומד בבסיס האלכסון של [[קנטור]].<br />
לצורך ההוכחה מסתמכים על כך שניתן למנות את כל האלגוריתמים בעולם, כך שבמניה זו יהיו כלולים כל האלגוריתמים. יש להדגיש כי כאן אנו עוסקים באלגוריתמים שמחזירים "כן" או "לא" בלבד, או שאינם עוצרים כלל (כלומר נכנסים ל[[לולאה]] אין סופית). לעיתיםלעתים נשתמש במניה שמכילה את כל האלגוריתמים של מחלקת [[סיבוכיות]] מסויימתמסוימת, ולא של כל האלגוריתמים כולם.<br />
מכיוון שקיימת מניה כזו (במסגרת זו לא נסביר כיצד), הרי שכל אלגוריתם יכול לקבל כ[[קלט]] את עצמו, או מספר המתאים למיקומו במניה זו.<br />
כעת, נתאר לעצמנו טבלה בעלת אורך אין סופי ורוחב אין סופי. כל שורה בטבלה מכילה מידע על אלגוריתם אחד מתוך האלגוריתמים שבמניה. כל עמודה מכילה מידע על קלט אחד, כאשר הקלטים הם המספרים 0 עד אין-סוף.
שורה 21:
נשאל את עצמנו את השאלה: האם בכל האלגוריתמים שנמצאים במניה שלנו יש אחד שמחשב את הפונקציה החדשה? התשובה היא כמובן: לא.<br />
כי נניח שאלגוריתם מספר x מחשב פונקציה זו, אז בפרט מה הוא מחזיר על הקלט x? אם לפי הטבלה הוא מחזיר "כן", אז לפי בניית הפונקציה החדשה הוא מחזיר "לא", ולהיפך - משמע שאלגוריתם מספר x '''לא''' מחשב את הפונקציה החדשה!<br />
יש לציין כי לעיתיםלעתים נשתמש בערכי הטבלה כפי שתואר כאן, ולפעמים לא נתעניין בערך המוחזר אלא בשאלה האם האלגוריתם עוצר. הפונקציה החדשה תהיה '''מוגדרת''' על קלט x אם האלגוריתם מספר x '''לא עוצר''', ולהיפך.<br />
להשלמת ההוכחה, יש להראות כי מחלקה כלשהי '''כן''' מכילה את הפונקציה החדשה שבנינו, וכך להראות שיש פונקציה שקיימת במחלקה ה"חזקה" ולא במחלקה ה"חלשה".<br />
 
שורה 29:
 
==מגבלות==
ניתן להראות כי שיטת הלכסון לא יכולה לעזור בהוכחה שמחלקה אחת "חזקה" יותר ממחלקה אחרת, עבור מחלקות מסויימותמסוימות.<br />
הדוגמאהדוגמה הידועה ביותר היא שלא ניתן להראות כ 'P!=NP' באמצעות שיטה זו.<br />
כדי להראות מגבלה של שיטת הלכסון, משתמשים במודלים של חישוב עם [[אורקל]], ונושא זה חורג מתחום ערך זה.