Complexity Course, Spring 2009, Tel Aviv University

> 1. what is the key property that separates L for NL? what can't a > machine in L do, that

Hi Ari, The complement of the question in this problem (Q6 in the quiz) is: for every two vertices x,

Ok, so I was mistaken after all since I mixed this question with the previous one (with question 3

לגבי 4, נדמה לי שזה בזכות החלק של "תוך t צעדים" - אתה מגביל את זמן הריצה של המכונה ל t

שאלה 1 נסמן ב- את זמן הריצה של מכונת טיורינג M על הקלט x. נניח שקיימת מכונות טיורינג אוניברסלית כך

הדרך השניה לא נכונה? אי אפשר ליצור את הגרף המשלים? On 8 אוגוסט, 16:28, odedr <ode...@gmail.com>

In Q4, use an easy reduction from VC (the problem is essentially equivalent, just in a different

Eugene is correct about 1. You need to verify that the path is simple, and this is something that we

יש באתר פתרונות: וזה פתרון של שאלה 2 http://www.cs.tau.ac.il/~odedr/teaching/complexity_spring_2009/

Sorry, my mistake: both E3SAT and 3SAT are of course easy for gap [9/2006,10/2006] (because a random

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

There is a trivial reduction from MAX-E5-SAT to MAX-5-SAT (because the former is a 'special case

This is something we taught last year, so you don't have to know it. (If you're interested,

thanks. On 2 אוגוסט, 16:43, Ido Ben Eliezer <idob...@gmail.com> wrote: > The solutions of

Hi, The exams and the final grades were submitted to the secretariat. In general, the final grade is

מקווה שהלך לכולם טוב... :) מתי יפורסם טופס הבחינה באתר? תודה, מרים

אם אין אני לי מי לי... אז אני אוסיף בעצמי את מה שביקשתי, אם מישהו עוד מתעניין באחת הסוגיות - לגבי

1 is also true, because TIME is a class of deterministic machines (ie, "simple" algorithms)

חייבים להשתמש בהוכחה שBPP מוכל בסיגמא 2 2009/7/2 itay <itay...@gmail.com> לגבי השאלה 4. תהי C

:) 2009/7/2 ptyl eyal <the....@gmail.com> שלוש שעות של שכרון חושים ...be gentle 2009/7/2 yuval

שים לב שרק אם ידוע ש*כן* קיים קירוב C, אז בעיות ה GAP האלה הן לא קשות. זה שלא קיים קירוב C לא בהכרח

נניח הקודקודים הם 1...n. 1. תן צבע כחול ל-1 ורשום לסרט הפלט 2. עבור כל הקודקודים i בין 2 ל n בצע: א.

Hi Itay, Noam, Here is an idea for a solution for cc-07-ab, question III-b: We show that SAT belongs

בנוסף לכך שאתה יכול לפתור את SAT במכונה מהסוג הזה (מכונת NL שבה מותר לחזור אחורה על סרט העד), חשוב

משהו כזה. כל פעם תבחר השמה למשתנה אחד ותבדוק מה התוחלת תהיה אם תיתן לו T ומה עם F. ככה תעבור משתנה

A לא בהכרח NP - קשה -- למעשה אין שוב סיבה מהנתון שהיא תהיה. גם העובדה שמובטח קירוב ל- B לא מבטיח

למדנו שתחולת גודל החתך המינימלי היא חצי ממספר הקשתות. מוכיחים ע"י הגרלה של מספר קבוצה ( 1 / 2 )

כן, במקרה הראשון הכל קורס ל-P במקרה השני הכל קורס ל-NP On Jul 2, 12:35 pm, אריאל <arieleva...@

I believe I have an alternative solution to part B. Since I used similar reasoning in other questions

עודד כתב פה אתמול שהרדוקציה היא לגאפ של [1, 15/16+eps] לכן הקירוב הכי טוב הוא 16/15+eps On 1 יולי, 20