שאלה מתורת החישוביות.

[אלוהים1980]

שאלה מתורת החישוביות.

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

 

[ahab]

בהצלחה! ../images/Emo8.gif

השפה המשלימה ל-SAT היא coNP-שלמה. אפשר להראות כי אם שפה coNP-קשה נמצאת ב-NP, אז coNP=NP. השאלה הזו, נכון להיום, היא בעיה פתוחה. אם תצליח לחשוב על אלגוריתם, אני אשמח אם תעדכן אותנו

 

[אלוהים1980]

הממ... ומה אם היא לא ב NP?

במקרה כזה אפשר להגיע למסקנה כלשהי לגבי השאלה האם P=NP? ועוד שאלה: בהנחה ש P שונה מ NP, האם קיימות שלוש שפות, L1, L2, L3 כך ש L1 מוכלת ב L2 שמוכלת ב L3, כך ש L1 ו L3 שייכות ל NPC ו L2 שייכת ל P?

 

[ahab]

לגבי השאלה הראשונה..

אם P=NP אז coNP=NP. אבל הכיוון ההפוך לאו דווקא נכון. (אתה מתכוון לשאלה 93 במקרה?)

 

[אלוהים1980]

אני מתכוון לשאלה 69.14

באוסף התרגילים של הקורס חישוביות בטכניון.

 

[ahab]

אה

אז לפי מה שכתבתי, אם SAT-complement לא ב-NP, אז coNP שונה מ-NP, וזה גורר כי P שונה מ-NP. (כן, אני מכיר את האוסף )

 

[אלוהים1980]

וואלה. אכן, פשוט ביותר. תודה ../images/Emo13.gif

 

[ahab]

ולשאלה השניה..

ודאי. קח עבור L3 איחוד של שפות.

 

[אלוהים1980]

משהו בסגנון הזה?

השפה הראשונה היא 3SAT - אוסף פסוקי ה CNF הספיקים שכל פסוקית בהם מורכבת משלושה ליטרלים. השפה השניה היא אוסף כל פסוקי ה CNF שכל פסוקית בהם מורכבת משלושה ליטרלים. השפה השלישית היא השפה השניה איחוד עם SAT.

 

[ahab]

כן, נראה לי שזה עובד

העיקר שבשפה L3 תצטרך לעבוד "קשה" כדי לבדוק חלק מהקלטים.

 

[אלוהים1980]

אפשר עוד אחת?

יחס S יקרא יחס מונוטוני אם לכל X1 X2 Y1 Y2 כך שהאורך של X1 קטן מהאורך של X2 וגם הזוג X1,Y1 שייכים ל S וגם X2,Y2 שייכים ל S גורר: האורך של Y1 קטן מהאורך של Y2. בהנחה ש P שונה מ NP: האם נכון לומר שלכל שפה L ב NP קיים יחס S מונוטוני חסום פולינומית וניתן לזיהוי פולינומי, כך שהשפה L היא אוסף כל השמאליים ביחס?