אלגוריתמים 2 – תרגול 1

ניר סון

בעיות חיפוש מול בעיות הכרעה

• בעיות הכרעה (הגדרה לא פורמלית): בעיות שהתשובה שלהן היא בוליאנית (true/false). בעיות כאלה נקראות גם שפות.

​

• בעיות חיפוש (הגדרה לא פורמלית): בעיות שהתשובה שלהן היא לא בוליאנית (אלא הפתרון עצמו).

​

• דוגמה:
• בהנתן גרף G ומספר טבעי k, האם קיימת בגרף קליקה בגודל k?
• בהנתן גרף G ומספר טבעי k, מצאו קליקה בגודל k בגרף (אם קיימת. אם לא החזירו null).

​

• בשיעורים הבאים נדבר כמעט ורק על בעיות הכרעה (שפות)
• נרצה להראות שבעיות חיפוש שקולות לבעיות הכרעה

​

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

בעיות חיפוש מול בעיות הכרעה

3-color

• 3-Color = {<G> | the vertices G can be colored with 3 colors, that that no two ends of an edge have the some color}

​

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

מהי בעיית החיפוש המתאימה?

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

​

נניח שיש לנו אלגוריתם שפותר את בעיית ההכרעה (מחזיר כן/לא האם יש 3 צביעה). יש לפתח אלגוריתם (שמשתמש באלגוריתם ההכרעה), אשר פותר את בעיית החיפוש

Self reduction for 3-col

P and NP

CNF-SAT & K-CNF-SAT

2-CNF-SAT is in P