שיחה:רדוקציה חישובית

איחוד

מה שאני מציע הוא לאחד את הערכים רדוקציה חישובית ורדוקציה פולינומית לערך רדוקציה. לא התרשמתי שיש צורך בשלושה ערכים שונים. רוזבאד - שיחה 21:02, 4 בדצמבר 2009 (IST)

המשך הדיון בשיחה:רדוקציה. תומר א. - שיחה 23:52, 4 בדצמבר 2009 (IST)

אוחד. את הערך רדוקציה כתבו GilCahana, רוזבאד, בוטים ומשתמשים אנונימיים. את כותבי הערך רדוקציה פולינומית ניתן לראות שם בלשונית הגירסאות הקודמות. תומר א. - שיחה - _{משנה ויקיפדית} 19:06, 23 בינואר 2010 (IST)

דוגמת הרדוקציה

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

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

מינוח לא מדויק

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

כנראה צריך להיות כתוב "NP-שלמות".

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