שאלות אמריקאיות

unread,

Aug 3, 2009, 5:13:00 AM8/3/09

to Complexity Course, Spring 2009, Tel Aviv University

שלום,

האם ישנה אפשרות לפרסם הסברים, אפילו של שורה או שתיים, לתשובות לשאלות
האמריקאיות המופיעות באתר?

תודה!

unread,

Aug 7, 2009, 6:28:33 AM8/7/09

to Complexity Course, Spring 2009, Tel Aviv University

We usually don't do this. If you have any specific questions, please
ask here.

-- Oded

unread,

Aug 7, 2009, 1:25:08 PM8/7/09

to Complexity Course, Spring 2009, Tel Aviv University

In the test, part A, question 8:
assuming that MAX-IS[a,b] is NP-Hard for 1 > b > a > 0....

why does argument 4 is true?
(Max-Clique is NP-Hard for every factor smaller than 1-a/1-b )

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

unread,

Aug 8, 2009, 3:13:29 AM8/8/09

to Complexity Course, Spring 2009, Tel Aviv University

בעיית קליק, בדומה לIS
קשה לקירוב לכל פקטור קבוע, בפרט לפקטור שצויין בשאלה (לא קשור לנתוני
השאלה)

On 7 אוגוסט, 20:25, "daniel.kle...@gmail.com"

Reply all

Reply to author

Forward