אלגוריתם לאס וגאס

אלגוריתם לאס וגאס
סיבוכיות זמן	O(n^2)
ממציא	לאסלו בבאי
נקרא על שם	לאס וגאס
הומצא	1979

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

דוגמה פשוטה היא מיון מהיר אקראי, כאשר איבר הציר נבחר באופן אקראי, אבל התוצאה תמיד ממוינת. ההגדרה הרגילה של אלגוריתם לאס וגאס כוללת את ההגבלה שתוחלת זמן הריצה תמיד תהיה סופית, כאשר התוחלת מתבצעת מעל מרחב המידע האקראי, או האנטרופיה, בהם האלגוריתם משתמש. הגדרה חלופית דורשת שאלגוריתם לאס וגאס תמיד יסתיים (יהיה יעיל), אך הוא עשוי לתת כפלט סמל שאינו חלק ממרחב הפתרונות כדי לדווח על כשל במציאת פתרון.^[1]

אלגוריתמים מסוג לאס וגאס הוצגו על ידי לסלו בבאי ב-1979, בהקשר של בעיית איזומורפיות גרפים, כזוג לאלגוריתם מונטה קרלו.^[2] ניתן להשתמש באלגוריתמים מסוג לאס וגאס במצבים בהם מספר הפתרונות האפשריים מוגבל, וכאשר אימות נכונותו של הפתרון המועמד הוא קל יחסית, בעוד חישוב הפתרון הוא מורכב.

מקור השם מהעיר לאס וגאס, אשר ידועה כסמל להימורים.

מחלקת סיבוכיות

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

מתקיים כי ${\textrm {ZPP}}={\textrm {RP}}\cap \,{\text{co}}\,{\textrm {-RP}}\!$ , דבר הקשור באופן הדוק עם הדרך שאלגוריתמים מסוג לאס וגאס נבנים לעיתים. כלומר המחלקה RP מורכבת מכל בעיות ההכרעה להן קיים אלגוריתם זמן-פולינומי אקראי המחזיר תשובה נכונה, כאשר התשובה הנכונה היא "לא", אבל רשאי לטעות בהסתברות מסוימת הרחוקה מ-1, כאשר התשובה היא "כן". כאשר קיים אלגוריתם כזה עבור בעיה והמשלימה שלה (התשובות "כן" ו "לא" מוחלפות), ניתן להריץ בו זמנית את שני האלגוריתמים ובאופן חוזר ונשנה: להריץ כל אחד מספר קבוע של צעדים, בתורנות, עד שאחד מהם מחזיר תשובה ודאית. זו הדרך הרגילה לבנות אלגוריתם לאס וגאס הפועל בתוחלת זמן פולינומית. שימו לב כי באופן כללי אין חסם עליון על זמן הריצה של המקרה הגרוע של אלגוריתם לאס-וגאס.

הקשר לאלגוריתם מונטה קרלו

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

ראו גם

קישורים חיצוניים

המדריך לאלגוריתמים ותורת החישוביות, CRC Press LLC, 1999.
אלגוריתם "לאס וגאס" ב"מילון של אלגוריתמים ומבני נתונים [באינטרנט], פאול א. בלק, ארצות הברית, המכון הלאומי לתקנים וטכנולוגיה. זמין מ: 17 יולי 2006. (גישה מאי 09, 2009)[1]

הערות שוליים

^ Steven D. Galbraith (2012). Mathematics of Public Key Cryptography. Cambridge University Press. p. 16. ISBN 978-1-107-01392-6.
^ László Babai, Monte-Carlo algorithms in graph isomorphism testing, Université de Montréal, D.M.S. No. 79-10.

[Galbraith2012-1] Steven D. Galbraith (2012). Mathematics of Public Key Cryptography. Cambridge University Press. p. 16. ISBN 978-1-107-01392-6.

[2] László Babai, Monte-Carlo algorithms in graph isomorphism testing, Université de Montréal, D.M.S. No. 79-10.

[1]

[2]