שאלה 1 במועד א
68 views
Skip to first unread message
toker
Aug 13, 2011, 11:48:47 AM8/13/11
to complex...@googlegroups.com
אם כבר מדברים על המבחן....
לגבי א', ב' וג' אני די סגור:
א. לא נכון ממשפט היררכיית המקום
ב. נכון לפי משפט Savitch
ג. נכון לפי ב'
לגבי ד' אני לא בטוח: האם זה שקול לשאלה L=NL? כי אמרנו בג' ש PolyL = NPolyL אבל L שייכת ל PolyL ו- NL שייכת ל NPolyL אז קיומה של שפה שלמה ב- PolyL גוררת ש L=NL...
לגבי ה' אני קצת אבוד...אשמח לשמוע את דעתכם...
תודה!!
Rotem Cohen gadol
Aug 13, 2011, 11:57:04 AM8/13/11
to Complexity סיבוכיות
ב-ד' הטענה לא נכונה מהסיבה שם הייתה קיימת שפה כזאת יוצא מצב שההיררכיה
קורסת בדומה לזה שתיהיה שפה שלמה בPH
אם היא בPolyL אז לבטח היא נמצאת ב L^k כלשהו ואז אם היא שלמה יש רדוקציה
מכל חזקה אחרת אליה וזה אומר שאין הבדל בין הרמות בניגוד למה שטענו ב-א'
קורסת בדומה לזה שתיהיה שפה שלמה בPH
אם היא בPolyL אז לבטח היא נמצאת ב L^k כלשהו ואז אם היא שלמה יש רדוקציה
מכל חזקה אחרת אליה וזה אומר שאין הבדל בין הרמות בניגוד למה שטענו ב-א'
לגבי ה' גם לדעתי היא לא נכונה אפשר לנסות להסביר את זה עם ד' כי בP יש
שפה שלמה בניגוד למה שקורה בד'
שי בן-משה
Aug 13, 2011, 12:05:59 PM8/13/11
to Complexity סיבוכיות
ד. הטענה לא נכונה. נניח שהיא כן אז זה אומר שיש שפה A שהיא PolyL שלמה.
אז גם יש K עבורו השפה A בL^K.
ניקח שפה B בL^(K+1) ומכיוון שA היא PolyL שלמה אז יש רדוקציה לוג' מB
לA, ולכן B תהיה גם בL^K.
מכאן ינבע L^K = L^(K+1), וזה יסתור את סעיף א', שהוא לא נכון.
אז גם יש K עבורו השפה A בL^K.
ניקח שפה B בL^(K+1) ומכיוון שA היא PolyL שלמה אז יש רדוקציה לוג' מB
לA, ולכן B תהיה גם בL^K.
מכאן ינבע L^K = L^(K+1), וזה יסתור את סעיף א', שהוא לא נכון.
ה. גם לא נכונה. אם PolyL=P אז יש שפה PolyL שלמה, כי יש שפות P שלמות,
בסתירה לסעיף ד'.
מקווה שעזרתי :)
toker
Aug 13, 2011, 2:56:59 PM8/13/11
to complex...@googlegroups.com
וואלה צודקים...תודה רבה!
Reply all
Reply to author
Forward
0 new messages