בתשובה למ. השור, 26/03/03 21:05
-- אזהרה: תגובה טיפה טכנית -- 137652
בועז • בתשובה למ. השור יום ד', 26/3/2003, 22:24
תראה, אם תצא בת-קול מהשמיים ותגלה לנו ש P שונה מ NP אז זה באמת לא יעזור לנו מיידית ליותר מדי דברים (למרות שיש דברים שנוכל להסיק מזה, כגון קושי של קירוב). אבל, בהחלט יש תקווה שכשנראה את ההוכחה ש P שונה מ NP, היא תיתן לנו קצת יותר מאשר עצם המשפט.

לגבי מה שאמרת:

1. השאלות לא ממש בלתי-תלויות. מה שידוע הוא:

א. אם יש one-way-function אז P שונה מ NP וכן קיים pseudorandom generator

ב. אם יש בעיה ב NP שקשה למעגלים לא יוניפורמיים אז קיים pseudorandom generator (מסוג שונה מא' אבל עדיין מתאים לדה-רנדומיזציה). באופן קצת יותר מוגבל זה נכון גם אם יש בעיה ב NP שקשה למכונות יוניפורמיות הסתברותיות.

ג. אם NP=P אז גם קיים pseudorandom generator (שים לב שבמקרה זה BPP=P).

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

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

דרך אגב, אני מניח שיהיה מאמץ דומה אם נגלה ש NP מוכל ב P/poly.

-----------

‏1 צריך יהיה לתת מנגנון timeout לאלגוריתם הזה ע"מ שלא ירוץ בזמן אינסופי. אפשר לעצור אותו אחרי כל מספר סופר פולינומי של צעדים.
-- אזהרה: תגובה טיפה טכנית -- 137660
מ. השור • בתשובה לבועז יום ד', 26/3/2003, 23:28
זה כבר נהיה קצת מדי טכני בשביל המדיום הזה. אני מתחיל להרגיש כמו עתודאי (סליחה כליל, גולגר). בכל אופן תודה על התשובה.
חזרה לעמוד הראשי המאמר המלא
מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים
האייל הקורא RSS מאמרים | כתבו למערכת | אודות האתר | טרם התעדכנת | ארכיון | חיפוש | עזרה | תנאי שימוש © כל הזכויות שמורות