בתשובה להאייל האלמוני, 13/06/08 19:53
כמה הערות 481338
אני לא מכיר מושג כזה, "קונסטרוקטיביות של אלגוריתם". בפרט אני לא רואה את ההבדל בינו ובין מה שאנחנו מכנים כאן בשם יוניפורמיות.

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

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

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