בתשובה לאלון עמית, 25/05/04 22:57
 |
|
 |
||
|
||||
 |
עד כמה שידוע לי, כל אלגוריתם פולינומיאלי ניתן להצגה כLP מאחר וזו בעיה P-שלמה, אבל זו לא הצגה מעניינת במיוחד. אני לא מומחה לאלגוריתמים אבל יש הרבה אלגוריתמים שאני מכיר והם לא LP (טרנספורם פוריה וכפל מטריצות מהיר, אדאבוסט, כל מני מבני נתונים). להרבה בעיות יש פתרונות פולינומיאלים ברגע שמבינים טוב יותר מהי משפחת הקלטים שעליה רוצים לעבוד, או שמבינים מה רוצים להשיג (למשל אם רוצים קירוב ולא פתרון מדויק). אני חושב שהבעיה העיקרית בלעשות תסריט כזה היום היא בטיחות (האקרים, התחזות וכו'), וכח חישוב בהחלט ישפר את הבטיחות. אחת הסיבות שמערכות היום לא בטוחות היא שכאשר יש בחירה בין יעילות לבטיחות הרבה פעמים בוחרים ביעילות. אם היו מאפשרים לך לכתוב תוכנה שיכולה להיות פי 10 יותר איטית מאשר המתחרות שלה, ולהשקיע פי 10 יותר משאבים בפיתוחה, היא היתה יכולה להיות גם הרבה יותר בטוחה. מעבר לזה, אחסון לא עוזר לממשלה לשלוט אם היא לא יכולה לסרוק ולהוציא מידע מהמאגר. לכן, אלגוריתמים טובים יותר לזיהוי שפות ותמונות, וכו' בהחלט יכולים לעשות שינוי מהותי במצב. |
 |
 |
 |
|
|
|
||
|
||||
|
נראה לי שקצת התרחקנו ממשמעות הטענה המקורית שלי, ולא התכוונתי ליצור מזה כזה דיון, אבל בכל זאת: אני עדיין סבור שיש *הרבה* יותר בעיות ב-NP מבעיות ב-P, בכל דרך שתנסה לספור; זאת מנסיוני (שאינו רב מדי) אבל גם מנסיונם של אחרים, נדמה לי. אשמח להמשיך לדון בכך ולבסס את הטיעון, אבל חשוב להבהיר שזה לא קשור לשאלה אילו בעיות ניתנות ל*קירוב* בזמן פולינומיאלי - תחום מעניין, חשוב, מאוד פרקטי אבל אחר. בקשר ל-LP, לא הכרתי את ההגדרה של P-שלמות ולא התכוונתי לזה, אלא רק לכך ששאלות רבות הניתנות לפתרון פולינומיאלי זוכות לכך ע"י הצגה "טבעית" כ-LP. אתה צודק שיש עוד הרבה אלגוריתמים פולינומיאליים וממש חבל שנתווכח. נדמה לי שאתה גם מנסה להצביע על העובדה שב"חיים האמיתיים" אין לפעמים חשיבות לשאלה אם הבעייה היא ב-P או לא: לפעמים יש אלגוריתם לא פולינומיאלי אבל מעשי מאוד, ולפעמים האלגוריתם הפולינומיאלי איטי נורא. גם עם זה אני מסכים. לעניינים המעשיים: אין לי איזו דעה מוצקה בנושא, אבל נראה לי שהמחסומים שיעמדו בפני מימשל שינסה להכריח את כולם לעבוד עם כסף אלקטרוני נתון למעקב הם פוליטיים וחברתיים הרבה יותר משהם חישוביים. בעצם, אולי להיפך: שיפורים בכוח חישוב ומזעור יוכלו אולי להפוך פרוטוקולים מוגנים לחלוטין למעשיים יותר, ואולי אז הציבור יתרצה (אם כי לא הייתי בונה על זה). |
|
|
|
|
|
|
||
|
||||
|
יש אמרה "למי שמחזיק פטיש כל העולם הוא מסמר". ייתכן שמי שמומחה בLP ינסה (לאו דווקא באופן מודע) להציג כל אלגוריתם כLP (במיוחד מאחר וזה אפשרי עקרונית תמיד). אני חושב גם שאין לנו באמת וויכוח. רק רציתי להציל את כבודם האבוד של מפתחי האלגוריתמים (שאני לא נמנה עליהם), מאחר ומי שקורא את ההערות שלך עלול היה להבין שכל התחום הזה מורכב רק מהאלגוריתם אחד, שפיתחו אותו כבר לפני כמה עשורים. גם לי אין דעה מוצקה בנושא של העניינים המעשיים. יש סיבה אחת שגורמת לי לחשוב שייתכן והטכנולוגיה היא המכשול ולא המכשולים הפוליטיים או החברתיים. אני כרגע חי בארה"ב ואני רואה איך חברה שהוקמה על בסיס של חשד לממשל מרכזי, עדיין מוכנה לקבל על עצמה המון פגיעות זוחלות בפרטיות. זה מתבטא בכרטיסי אשראי ודירוג אשראי, במאגרי נתונים בבתי מרקחת (פה המחשב של הרשת זוכר מי אתה, מה הכתובת והטלפון שלך, ומה התרופה שרשמו לך), בפלאפונים, ב EZPASS ועוד המון דברים אחרים. |
|
|
|
|
|
|
||
|
||||
|
אה. לא התכוונתי, כמובן, להוליך את כבודם של מפתחי אלגוריתמים לאיבוד (ודווקא נמניתי על שורותיהם, פעם). | |
|
|
| חזרה לעמוד הראשי | המאמר המלא |
| מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים | |
 RSS מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש
|
© כל הזכויות שמורות |