נושאים פעיליםנושאים פעילים  הצגת רשימה של חברי הפורוםרשימת משתמשים  חיפוש בפורוםחיפוש  עזרהעזרה
  הרשמההרשמה  התחברותהתחברות RSS עדכונים
מדעי המחשב
RSS UnderWarrior Forums : RSS מדעי המחשב
נושא

נושא: שאלות על P וNP

 שליחת תגובהשליחת נושא חדש
כותב
הודעה << נושא קודם | נושא הבא >>
תמר
אורח
אורח


הצטרף / הצטרפה: 01 October 2003
משתמש: אונליין
הודעות: 12647
נשלח בתאריך: 06 September 2009 בשעה 14:30 | IP רשוּם
ציטוט תמר

1. איך מוכיחים שP סגורה לשרשור?

2. אלו שפות שייכות לP לNP:

   א. שפת הפסוקים בצורת CNF שיש להם לפחות 2 השמות מספקות.

   ב. שפת הפסוקים שאינם טאוטולוגיה.

   ג. שפת הפסוקים הספיקים בצורת DNF.                                                    

                                    
חזרה לתחילת העמוד הצג את כרטיס החבר של תמר חפש הודעות אחרות של תמר בקר בדף הבית של תמר
 
green
אורח
אורח


הצטרף / הצטרפה: 01 October 2003
משתמש: אונליין
הודעות: 12647
נשלח בתאריך: 08 September 2009 בשעה 08:13 | IP רשוּם
ציטוט green
1) תיקח שתי שפות ב-P , יש להן מכונת טיורינג פולי, עכשיו עבור כל מילה תנסה לפרק אותה לרישא וסיפא (מספר האפשרויות לעשות זאת הוא כאורך המילה), ותריץ את המכונה הראשונה על הרישא והשנייה על הסיפא. אם הרישא נמצאת השפה הראשונה והסיפא בשנייה סיימת.
אחרת תמשיך ככה ואם אף רישא ואף סיפא לא נמצאות שתיהם בשתי השפות אז המילה לא בשפה. (תחשוב על כל הצעדים ותראה שזו מ"ט פולי).

2) א- NPC, פשוט תראה רדוקציה מ-CNF ע"י שתחבר עוד פסוקית שהיא טאוטולוגיה.
ב- שוב אפשר לעשות רדוקציה מ-CNF, פשוט תחבר עוד פסוקית שיש שם ליטרל שלא מופיע באף פסוקית אחרת. ככה זה מבטיח שהפסוק שלך הוא לא טאוטולוגיה
ג- שוב אפשר לעשות רדוקציה מ-CNF , לא יודע אם למדת את זה אבל אפשר להפוך כל פסוק לוגי לפסוק מהצורה DNF.

בקיצור כל השפות הללו הם NPC , והם שייכות ל-P אמ"מ P=NP
חזרה לתחילת העמוד הצג את כרטיס החבר של green חפש הודעות אחרות של green בקר בדף הבית של green
 
תמר
אורח
אורח


הצטרף / הצטרפה: 01 October 2003
משתמש: אונליין
הודעות: 12647
נשלח בתאריך: 09 September 2009 בשעה 01:56 | IP רשוּם
ציטוט תמר

תודה רבה!

אפשר עוד שאלה - על רדוקציות?

תהי TOT קבוצת מספרי התכניות שעוצרות לכל קלט.
תהי EMPTY קבוצת מספרי התכניות שלא עוצרות על אף קלט.
האם יש רדוקציה מ- TOT ל-EMPTY ? [נראה לי שלא, אבל כיצד מוכיחים זאת?]
חזרה לתחילת העמוד הצג את כרטיס החבר של תמר חפש הודעות אחרות של תמר בקר בדף הבית של תמר
 

אם ברצונך להגיב לנושא זה עליך קודם להתחבר
אם אינך רשום/ה כבר עליך להרשם

  שליחת תגובהשליחת נושא חדש
גרסת הדפסה גרסת הדפסה

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