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