תשובות לשאלות האמריקאיות במבחן

Carmel Gridinger

unread,

Jul 12, 2010, 9:19:48 AM7/12/10

to Computational Complexity, Spring 2010

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

לחלקנו יש הרגשה שטעו לנו בבדיקה ונשמח לדעת מה התשובות הנכונות.

תודה

Ido Ben Eliezer

unread,

Jul 12, 2010, 9:46:08 AM7/12/10

to computational-comp...@googlegroups.com

אין לי את הבחינה מולי כרגע, אבל באופן לא פורמלי (סדר השאלות שונה בין הגירסאות):

בשאלה לגבי ההיררכיה הפולינומית (מה קורה אם NP שווה ל- coRP), התשובה היא א', ההיררכיה קורסת ל- NP.

בשאלת הזיכרון, הטענה תמיד לא נכונה (ב') לפי משפט היררכיית הזיכרון.

coRP תמיד מוכל בסיגמא 2 ופי 2 (התשובה היא א'), לפי משפט סיפסר.

בעיית ה- Gap-IS שצוינה בהכרח ב- P (ניתן לראות שבעיה זו שקולה לבעיית Gap-VC שניתנת להכרעה בעזרת אלג' 2-קירוב).

2010/7/12 Carmel Gridinger <grid...@gmail.com>

Indigon

unread,

Jul 12, 2010, 9:58:29 AM7/12/10

to Computational Complexity, Spring 2010

על מה אתם מדברים
איפה יש תוצאות? O_O

On Jul 12, 4:46 pm, Ido Ben Eliezer <idob...@gmail.com> wrote:
> אין לי את הבחינה מולי כרגע, אבל באופן לא פורמלי (סדר השאלות שונה בין
> הגירסאות):
>
> בשאלה לגבי ההיררכיה הפולינומית (מה קורה אם NP שווה ל- coRP), התשובה היא א',
> ההיררכיה קורסת ל- NP.
>
> בשאלת הזיכרון, הטענה תמיד לא נכונה (ב') לפי משפט היררכיית הזיכרון.
>
> coRP תמיד מוכל בסיגמא 2 ופי 2 (התשובה היא א'), לפי משפט סיפסר.
>
> בעיית ה- Gap-IS שצוינה בהכרח ב- P (ניתן לראות שבעיה זו שקולה לבעיית Gap-VC
> שניתנת להכרעה בעזרת אלג' 2-קירוב).
>

> 2010/7/12 Carmel Gridinger <gridin...@gmail.com>

Carmel Gridinger

unread,

Jul 12, 2010, 9:59:07 AM7/12/10

to computational-comp...@googlegroups.com

יש מחברות סרוקות
אבל עוד אין ציונים סופיים

2010/7/12 Indigon <shay.h....@gmail.com>

Carmel Gridinger

unread,

Jul 12, 2010, 10:01:51 AM7/12/10

to computational-comp...@googlegroups.com

אפשר לשאול לגבי השאלה האחרונה איך זה מסתדר עם העובדה שלמדנו ש-gap is ו- gap clique קשות לקרוב לכל פקטור קבוע?

2010/7/12 Ido Ben Eliezer <ido...@gmail.com>

Ido Ben Eliezer

unread,

Jul 12, 2010, 10:15:11 AM7/12/10

to computational-comp...@googlegroups.com

כפי שהודגש בכיתה -- העובדה שקשה לקרב בכל פקטור קבוע אינה אומרת שכל בעיית Gap היא קשה. הגרירה היא רק בכיוון ההפוך.

2010/7/12 Carmel Gridinger <grid...@gmail.com>

Eliran Moyal

unread,

Jul 12, 2010, 10:16:38 AM7/12/10

to computational-comp...@googlegroups.com

תודה עידו,

תוכל להגיד גם מה הניקוד של הסעיפים בשאלה ב' ?

בתאריך 12 ביולי 2010 17:15, מאת Ido Ben Eliezer <ido...@gmail.com>:

Ido Ben Eliezer

unread,

Jul 12, 2010, 10:20:23 AM7/12/10

to computational-comp...@googlegroups.com

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

2010/7/12 Eliran Moyal <eliran...@gmail.com>

Alon Dener

unread,

Jul 12, 2010, 10:27:15 AM7/12/10

to computational-comp...@googlegroups.com

אתה יכול בבקשה לפרט בדיוק איך הולך החישוב הזה שתיארת?

בתאריך 12 ביולי 2010 17:20, מאת Ido Ben Eliezer <ido...@gmail.com>:

merav

unread,

Jul 12, 2010, 1:29:42 PM7/12/10

to Computational Complexity, Spring 2010

אפשר לפרם את הטופס של הבחינה?

On 12 יולי, 17:27, Alon Dener <alonde...@gmail.com> wrote:
> אתה יכול בבקשה לפרט בדיוק איך הולך החישוב הזה שתיארת?
>

> בתאריך 12 ביולי 2010 17:20, מאת Ido Ben Eliezer <idob...@gmail.com>:

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

> > 2010/7/12 Eliran Moyal <eliran.moy...@gmail.com>

>
> > תודה עידו,
> >> תוכל להגיד גם מה הניקוד של הסעיפים בשאלה ב' ?
>

> >> בתאריך 12 ביולי 2010 17:15, מאת Ido Ben Eliezer <idob...@gmail.com>:
>
> >> כפי שהודגש בכיתה -- העובדה שקשה לקרב בכל פקטור קבוע *אינה* אומרת שכל

> >>> בעיית Gap היא קשה. הגרירה היא רק בכיוון ההפוך.
>

> >>> 2010/7/12 Carmel Gridinger <gridin...@gmail.com>

>
> >>>> אפשר לשאול לגבי השאלה האחרונה איך זה מסתדר עם העובדה שלמדנו ש-gap is
> >>>> ו- gap clique קשות לקרוב לכל פקטור קבוע?
>

> >>>> 2010/7/12 Ido Ben Eliezer <idob...@gmail.com>

>
> >>>> אין לי את הבחינה מולי כרגע, אבל באופן לא פורמלי (סדר השאלות שונה בין
> >>>>> הגירסאות):
>
> >>>>> בשאלה לגבי ההיררכיה הפולינומית (מה קורה אם NP שווה ל- coRP), התשובה היא
> >>>>> א', ההיררכיה קורסת ל- NP.
>
> >>>>> בשאלת הזיכרון, הטענה תמיד לא נכונה (ב') לפי משפט היררכיית הזיכרון.
>
> >>>>> coRP תמיד מוכל בסיגמא 2 ופי 2 (התשובה היא א'), לפי משפט סיפסר.
>
> >>>>> בעיית ה- Gap-IS שצוינה בהכרח ב- P (ניתן לראות שבעיה זו שקולה לבעיית
> >>>>> Gap-VC שניתנת להכרעה בעזרת אלג' 2-קירוב).
>

> >>>>> 2010/7/12 Carmel Gridinger <gridin...@gmail.com>

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

> >>>>>> תודה-הסתר טקסט מצוטט-
>
> -הראה טקסט מצוטט-

Ofir

unread,

Jul 12, 2010, 1:31:42 PM7/12/10

to Computational Complexity, Spring 2010

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

Ido Ben Eliezer

unread,

Jul 12, 2010, 2:10:11 PM7/12/10

to computational-comp...@googlegroups.com

לא בהכרח

2010/7/12 Ofir <ofir....@gmail.com>

Reply all

Reply to author

Forward