21 הבעיות ה-NP שלמות של קארפ

במדעי המחשב, 21 הבעיות ה-NP שלמות של קארפ הן רשימה של 21 בעיות שהציג ריצ'רד קארפ במאמרו משנת 1972, reducibility among combinatorial prolems. המאמר הגיע מעט אחרי פרסום משפט קוק לוין, בו הוכח שבעיית הספיקות קשה לפחות כמו כל בעיה אחרת בNP. במאמר הציג קארפ את המושג NP שלמות, והראה על 21 בעיות שהן NP שלמות. מאז הוכחו עוד אלפי בעיות כ-NP שלמות, והשאלה האם P=NP (שהוצגה גם היא במאמר) הפכה לאחת השאלות הפתוחות המרכזיות במדעי המחשב.

הבעיות

להלן הרשימה של 21 הבעיות. בכל בעיה מוצגת בקצרה הרדוקציה שהציג קארפ: פונקציה מבעיה NP שלמה אחרת אליה, שמוכיחה שהיא קשה לפחות כמוה.

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

בעיית הספיקות

בהינתן פסוק בצורת CNF, כלומר אוסף פסוקיות עם סימני או בתוכן וסימני וגם ביניהן, האם יש השמה שתספק את כולן?

בעיה זו הוכחה על ידי קוק כ-NP שלמה.

תכנון ליניארי בשלמים

בהינתן אוסף משתנים עם אילוצים ליניאריים עליהם, האם יש לה פתרון עם ערכים בוליאניים (0 או 1)?

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

רדוקציה: מבעיית הספיקות. מחליפים כל פסוקית באי-שוויון, שבו ליטרל מוחלף במשתנה $x$, ושלילת הליטרל - בביטוי $1-x$. סכום משתנים אלה לפחות 1. כך השמה מספקת תוחלף בהשמה של 1 למשתנים שהם T, ו-0 למשתנים שהם F.

בעיית הקליקה

בהינתן גרף G ומספר k, האם יש בגרף קליקה בגודל k?

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

בעיית אריזת הקבוצות

בהינתן משפחת קבוצות S ומספר l, האם יש במשפחה l קבוצות זרות בזוגות?

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

בעיית כיסוי קודקודים

בהינתן גרף G ומספר l, האם יש קבוצת קודקודים שגודלה לכל היותר l כך שכל קשת נוגעת בקודקוד מהקבוצה?

רדוקציה: מבעיית הקליקה. הגרף נלקח להיות הגרף המשלים, והמספר k - מספר הקודקודים בגרף פחות המספר המקורי. כך המשלים של קליקה יהיה כיסוי קודקודים בגרף החדש.

בעיית כיסוי הקבוצות

בהינתן משפחת קבוצות S ומספר k, האם יש במשפחה k קבוצות שאיחודן שווה לאיחוד הקבוצות?

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

feedback node set

בהינתן גרף מכוון H ומספר k, האם יש קבוצת קודקודים בגודל k כך שכל מעגל עובר בקודקוד מהקבוצה?

רדוקציה: מבעיית כיסוי קודקודים. הופכים כל קשת בגרף המקורי (הלא מכוון) לשתי קשתות, אחת בכל כיוון. כך כיסוי יהפוך לקבוצת feedback.

feedback arc set

בהינתן גרף מכוון H ומספר k, האם יש קבוצת קשתות בגודל k כך שכל מעגל עובר בקשת מהקבוצה?

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

מעגל המילטוני מכוון

בהינתן גרף מכוון, האם יש בו מעגל שעובר בכל הקודקודים?

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

מעגל המילטוני לא מכוון

בהינתן גרף לא מכוון, האם יש בו מעגל שעובר בכל הקודקודים?

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

3SAT

בהינתן פסוק CNF שבכל פסוקית בו יש עד שלושה ליטרלים, האם הוא ספיק?

רדוקציה: מבעיית הספיקות. כל עוד הבעיה איננה 3CNF, מוסיפים משתנה חדש ובעזרתו מפצלים את אחת הפסוקיות לפסוקית עם 3 משתנים ועוד פסוקית עם פחות משתנים מהמקורית, וכן עוד פסוקיות שמבטיחות שהפסוק החדש יהיה ספיק אם ורק אם המקורי ספיק. כיוון שבפעולה זו הורדנו ב-1 את כמות המשתנים מאחת הפסוקיות, אפשר להמשיך עד שמקבלים בעיית 3SAT.

מספר כרומטי

בהינתן גרף G ומספר k, האם אפשר לצבוע את הקודקודים ב-k צבעים כך שאף קשת לא תחבר קודקודים מאותו הצבע?
(זה היה הנוסח המקורי; היום ידוע שהבעיה NP שלמה גם ל-k קבוע, אם k>2).

רדוקציה: מ3SAT. יוצרים קודקודים מהמשתנים ומהפסוקיות ומחברים אותם כך שכל משתנה חייב להיצבע בצבע הפסוקית בה הוא מקבל T.

כיסוי קליקות

בהינתן גרף G ומספר l, האם ניתן למצוא l קליקות שאיחודן מכסה את כל הגרף?

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

כיסוי מדויק

בהינתן משפחת קבוצות, האם קיימות מתוכן קבוצות זרות בזוגות שאיחודן שווה לאיחוד כל המשפחה?

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

hitting set

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

רדוקציה: מבעיית הכיסוי המדויק. האלמנטים הם הקבוצות בבעיית המקורית; לכל אלמנט בבעיה המקורית, מסתכלים על קבוצת כל הקבוצות שהכילו אותו, וכך מקבלים את משפחת הקבוצות. כך הכיסוי המדויק הופך ל-hitting set.

בעיית העץ של שטיינר

בהינתן גרף G עם משקלים על הקשתות, קבוצת קודקודים N ומספר טבעי k, האם יש ל-G תת-עץ שמכיל את כל קודקודי N?

רדוקציה: מבעיית הכיסוי המדויק. קודקודי הגרף החדש הם האלמנטים בבעיה המקורית, הקבוצות, וקודקוד חדש. יש קשת מאלמנט לקבוצה אם הוא נמצא בה (במשקל 0), ומהקודקוד החדש לכל קבוצה (במשקל שהוא גודל הקבוצה). הקבוצה N היא האלמנטים והקודקוד החדש, k הוא מספר האלמנטים. כך כיסוי מדויק הופך לעץ בו הקודקוד החדש מתחבר לקבוצות בכיסוי המדויק, והן מתחברות לכל הקודקודים שבהן, משקל העץ הזה בדיוק k.

התאמה 3 ממדית

בהינתן קבוצה סופית T ותת קבוצה U של $T\times T\times T$, האם קיימת קבוצה $W\subset U$ כך ש-|T|=|W| שכל שני אלמנטים בה שונים בכל הקואורדינטות?

רדוקציה: מבעיית הכיסוי המדויק. T הוא זוגות של קבוצה ואלמנט שנמצא בה. להגדרת U מגדירים לכל קבוצה S תמורה שיש לה מעגל על איברי S. לוקחים את U להיות שהדרך היחידה למצוא התאמה היא להעביר את האיברים מאחד לשני עבור קבוצות שמשתתפות בכיסוי, ולהשאיר אותם במקום עבור קבוצות שלא משתתפות בכיסוי.

תרמיל הגב

בהינתן קבוצת מספרים $a_{1},...,a_{n}$ ומספר נוסף b, האם יש תת-קבוצה שלהם שסכומה בדיוק המספר הנוסף?
כיום מקובל לקרוא בעיית תרמיל הגב לבעיה אחרת, ולבעיה הזאת לקרוא בעיית הסכומים החלקיים.

רדוקציה: מבעיית הכיסוי המדויק. כל קבוצה מוחלפת במספר שמייצג את הקבוצה בבסיס ספירה d, כאשר d הוא מספר הקבוצות ועוד 1. כלומר, בבסיס d, למספר ה-i יש 1 במקום ה-j אם בקבוצה ה-i יש את האלמנט ה-j, אחרת 0. b הוא המספר 11...1 בבסיס d. כך הקבוצות שבכיסוי המדויק הופכות למספרים שסכומם הוא 11...1.

סידור עבודות

בהינתן רשימת עבודות, שלכל אחת מהן זמן שלוקח לבצע, זמן אחרון לביצוע, וקנס במידה והיא לא מבוצעת עד סוף הזמן, וכן מספר k, האם ניתן לסדר את העבודות כך שסך הקנסות לא יעלה על k?

רדוקציה: מבעיית תרמיל הגב. את המספר $a_{i}$ הופכים לבעיה שהזמן שלוקח לבצע הוא $a_{i}$, הזמן האחרון הוא $b$, והקנס הוא $a_{i}$. k הוא b. כך הדרך היחידה להימנע מקנסות היא להתחיל מבעיות שמסתכמות ל-b.

בעיית החלוקה

בהינתן וקטור $c_{1},...,c_{m}$ של מספרים שלמים, האם יש שתי תתי קבוצות זרות שאיחודן הוא כל הווקטור, כך שסכום המספרים בשתי הקבוצות שווה?

רדוקציה: מבעיית תרמיל הגב. המספרים יהיו $a_{1},...,a_{n},b+1,\sum a_{i}+1-b$. כך הדרך היחידה לחלק באופן שווה היא בצד אחד קבוצה מהווקטור המקורי שסכומה b, יחד עם האיבר $\sum a_{i}+1-b$, ובצד השני כל השאר.

חתך מקסימלי

בהינתן גרף עם משקלים טבעיים לקשתות ומספר W, האם יש חלוקה של הקודקודים לשתי קבוצות כך שסכום הקשתות בין הקבוצות עולה על W?

רדוקציה: מבעיית החלוקה. הגרף הוא הגרף המלא שקודקודיו מייצגים את המספרים, ומשקל הקשת מ-i ל-j הוא $c_{i}c_{j}$. כמו כן, W הוא ${\frac {\sum c_{i}^{2}}{4}}$. כך רק חלוקה שווה תתן חתך גדול מספיק (נובע מאי שוויון קושי שוורץ).

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

• Richard Karp, reducibility among combinatorial prolems

הערות שוליים

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

3514432321 הבעיות ה-NP שלמות של קארפ