 |
מצטער, אני מאוד לא אוהב לקרוא טקסטים שהם פחות מברורים לגמרי. אם אתה מעוניין בדעתי, אעדיף למסור לך אותה בצורת הסבר מחדש של הנושא, בלי לנסות לפענח - איתך הסליחה - את מה שכתבת.
ידוע שכל בעיה ב-NP, ניתן, בזמן פולינומי, להמיר בבעיית SAT. כלומר, אם אתה רוצה לדעת, למשל, אם יש מעגל המילטוני בגרף שעובר דרך כל הקודקודים, אתה יכול, בזמן פולינומי, ליצור פסוק בוליאני שניתן לסיפוק אם ורק אם היה בגרף שהתחלת ממנו את התהליך מעגל כנ"ל. בשלב הזה, אם מישהו יודע לפתור את SAT בזמן פולינומי, אתם יכולים לעבוד ביחד בכדי לפתור בזמן פולינומי את הבעיה המקורית שלך: אתה תיקח את הבעיה שלך, תמיר אותה בבעית SAT, תמסור אותה לבחור שיודע לפתור בעיות SAT, הוא יחזיר לך תשובה, ואתה תחזיר את התשובה שקיבלת ממנו. כל אחד משני השלבים נעשה בזמן פולינומי, ויחד זה עדיין פולינומי.
כלומר, יוצא שאם את בעית SAT ניתן לפתור בזמן פולינומי, אז כל בעיה ב-NP ניתנת לפתירה בזמן פולינומי, ע"פ התהליך הנ"ל (אותו לא תיארתי במלואו. אמרתי שידוע שאפשר לבצע המרה כזאת לכל בעיה ב-NP, אבל לא אמרתי איך).
חשוב לשים כאן לב שהבעיה שלך עשויה להיות הרבה יותר פשוטה מהבעיה שאתה מוסר לו הלאה. לדוגמה, אתה יכול להתמודד עם הבעיה המאוד פשוטה של "האם המספר שאני עומד מולו כרגע הוא המספר 31, או כל מספר אחר?" במקרה המנוון הזה, אתה יכול לפתור בקלות את הבעיה, ואז להעביר הלאה, לבחור שפותר את SAT, במידה וקיבלת את המספר 31, את הפסוק "א' או ב"', ובמידה וקיבלת מספר אחר, את הפסוק "א' או לא א"'. התשובה שלו לראשון תהיה "כן", ולשני "לא", אבל אתה לא תלמד מכך שום דבר חדש.
מה שאתה מחפש להוכיח הוא ש-SAT ניתנת לפתירה בזמן פולינומי. קלאסית, אתה תנסה לעשות את זה על ידי הצגת אלגוריתם שפותר את SAT בזמן פולינומי. דרך אחת לעשות את זה היא להראות שיש בעיה אחרת, שניתן לפתור אותה בזמן פולינומי, ושניתן להמיר *את SAT בבעיה החדשה הזאת בזמן פולינומי*. שים לא - לא את הבעיה החדשה בבעיית SAT, אלא את בעיית SAT בבעיה החדשה.
|
 |
RSS מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש