בתשובה לירדן ניר-בוכבינדר, 13/05/06 21:31
מה שירדן אמר, בערך. 385090
כולנו יודעים שלזהות הוכחה הרבה יותר קל מלחבר הוכחה.
אם חלילה יתגלה ש-P=NP, העובדה הזו לא תשתנה. מה שישתנה תהיה המשמעות שאנו מעניקים להגדרה המתמטית של P: לא יהיה ניתן יותר לומר שהיא מכילה רק שפות קלות-להכרעה, ונצטרך לאפיין את המושג "קל לחישוב" בצורה יותר עדינה.
מה שירדן אמר, בערך. 385155
אני לא מבין למה זה נכון. כבר עכשיו P מכילה גם שפות שאפשר להכריע רק בזמן שהוא פולינום בחזקת גוגול (אני בטוח שאפשר להנדס כזו שפה, לא?), אז כבר עכשיו קשה להגיד שזה "קל להכרעה".
מה שירדן אמר, בערך. 385188
נכון, הגזמתי לגבי המשמעות של P. היא מכילה גם הרבה דברים מאוד קשים להכרעה. אני אצטרך לחשוב על זה, כנראה ששוויון אינו בהכרח אסון..
מה שירדן אמר, בערך. 385217
הוא *עלול* להיות אסון למי שמשתמש בהצפנה (ה"עלול" מגיע מירדן).
מה שירדן אמר, בערך. 385239
אולי אני מפספס משהו ממש בסיסי אבל אני לא משוכנע שזה נכון. אתה יכול לחשוב על הוכחה? נניח שהמודל שלנו הוא מכונת טיורינג (או כל מודל אחר שאתה מעדיף).
מה שירדן אמר, בערך. 385242
אתה לא משוכנע שמה נכון? שקיימות בעיות שהפתרון שלהם הוא חזקה בגודל הזה? זו תוצאה של מה שמכונה Time hierarchy theorem.

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

אולי ההוכחה שיש בויקיפדיה האנגלית כן קונסטרקטיבית:

מה שירדן אמר, בערך. 385250
אתה צודק. זכרתי שיש משפט היררכיה של המקום אבל לא משפט היררכיה (פולינומי) של הזמן. טעות שלי.
מה שירדן אמר, בערך. 385253
עד כמה שאני מבין (למרות שאני קצת פחות סומך על עצמי כרגע) ההוכחה (שאני מכיר) היא כן קונסטרוקטיבית. מוכיחים ששפת כל המכונות M והקלטים x כך ש- M מקבלת את x בפחות מ- f(|x|) צעדים היא כריעה בזמן f^3 (נגיד) ולא כריעה בזמן f(n/2).

לכן לכל n^k קל להראות שפה פולינומית שלא חשיבה ב- n^k.
מה שירדן אמר, בערך. 385247
מה של גוגול? אולי התכוונת לצ'כוב?
מה שירדן אמר, בערך. 385248
"This article is about the large number. For the Internet company, see Google. For the author, see Gogol"

http://en.wikipedia.org/wiki/Googol
מה שירדן אמר, בערך. 387649
את הסופר אני לא מכיר, אבל מסתבר שיש קשר בין מנוע החיפוש לבין המספר בעל מאה האפסים. למעשה, השם Google מקורו כולו בעיוות שם המספר, שנעשה בטעות על ידי מפתחי המנוע.
מה שירדן אמר, בערך. 387652
כן, זה אחד מפרטי הטריוויה הרבים על החברה הזו (ידעת שה-"Page rank" נקרא על שם פייג', אחד ממקימי החברה?). מצאתי את עצמי פעם אומר "גוגל" במקום "גוגול", למרבה המבוכה.

אתה לא מכיר את גוגול או שלא קראת את גוגול?
מה שירדן אמר, בערך. 387679
לא מכיר, למרבה הבושה.
מה שירדן אמר, בערך. 387691
בשביל זה יש ויקיפדיה (ותרגומים לעברית של ספרים שלו).

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

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