בתשובה להאייל האלמוני, 13/06/08 19:06
 |
|
 |
||
|
||||
 |
שוב, אם ל*כל* אורך אפשר היה למצוא את המעגל ששובר את ההצפנה, ובהנחה (שאתה מוזמן לחלוק עליה) שהאדם לא חזק חישובית ממכונת טיורינג, פירוש הדבר היה שמשפחת המעגלים הזו היא יוניפורמית. עזוב אותך לרגע מהצפנה. מדברים על השפה האונרית שבה כל מילה מייצגת קידוד של מכונת טיורינג+קלט, ובעיית ההכרעה שלנו היא לזהות בדיוק את אלו שעוצרות על המילה הריקה. האם קיים מעגל שפותר את הבעיה לכל אורך מילה אפשרי? (כמובן). האם, כשנותנים לנו אורך ספציפי, יש סיכוי שאם נעבוד ממש ממש קשה נצליח למצוא את התשובה, תמיד, לכל אורך? אם כן, האם לא פתרנו את בעיית העצירה? אם לא, מה ההבדל בין זה ובין הדוגמה הקריפטוגרפית? ("הקבוצה המלאה" היא תזכורת לימי דיון 1571 העליזים.) |
 |
 |
 |
|
|
|
||
|
||||
|
אני מבין שאתה רוצה שאני אחלוק על ההנחה שלך אבל היא לא ממש רלוונטית לדיון שלנו. נשמע כאילו הבעיה שלך היא לא היוניפורמיות של האלגוריתם אלא הקונסטרוקטיביות שלו. באופן אנלוגי לפסקה השניה שלך, נגיד ש(כל) מה שאנחנו יודעים הוא שבעיה מסוימת היא ב- P. האם זה אומר שאם נעבוד מאוד קשה נמצא את האלגוריתם הפולינומי שפותר אותה? |
|
|
|
|
|
|
||
|
||||
|
אני לא מכיר מושג כזה, "קונסטרוקטיביות של אלגוריתם". בפרט אני לא רואה את ההבדל בינו ובין מה שאנחנו מכנים כאן בשם יוניפורמיות. אני לא בטוח אם קיימת הוכחה או לא לכך שמה שאתה מתאר בפסקה השנייה הוא בלתי כריע; איכשהו, נראה לי שהוא אכן כזה (דהיינו, אין אפילו אלגוריתם שמכריע בהינתן מכונת טיורינג האם היא פולינומית או לא - אולי אני טועה, ואולי יש לזה הוכחה טריוויאלית שאני לא חושב עליה כרגע). |
|
|
|
|
|
|
||
|
||||
|
אויש, אני כזה טמבל. מן הסתם לא קיים אלגוריתם שכזה וההוכחה אכן טריוויאלית (אם יש, נפתור את בעיית העצירה כך - בהינתן M ו-x, נבנה מכונה שעל כל קלט מריצה את M על x ועוצרת מייד אם M עצרה על x. היא פולינומית בגודל הקלט שלה אם ורק אם M עוצרת על x). | |
|
|
|
|
|
||
|
||||
|
קונסטרוקטיביות היא לא תכונה של אלגוריתם אלא של הוכחת/הנחת קיום. ההוכחה היא קונסטרוקטיבית אם היא מכילה את האלגוריתם באופן מפורש. | |
|
|
| חזרה לעמוד הראשי | המאמר המלא |
| מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים | |
 RSS מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש
|
© כל הזכויות שמורות |