מבחן 2007 - א - ב Lin2

[Noam Schachter]

מבחן 2007 סמסטר א - מועד ב

בשאלה 2 - ג צריך להראות שקיים אלגוריתם קירוב לבעיית -2CSG (שנקראת
בבעיה UG)) שמבטיח יחס קירוב c אםם קיים אלגוריתם קירוב פולינומיאלי
לבעיית Lin2 שמבטיח אותו יחס קירוב.

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

באותו מבחן, שאלה 2-ב שואלים האם SAT שייכת למחלקה C(1/n) ,
האינטואיציה שלי היא שזה שקול לבעיית P=NP, אבל איך ניתן להוכיח?

[itay]

צריך לעשות רדוקציה:
Gap-UG(2)[a,ca] <= Gap-Lin2[a,ca]
כל צומת הופך למשתנה.
כל אילוץ של קשת )u,v) הופך למשוואה באופן הבא:
אם האילוץ הוא: ((0,0), (1,1) } אז המשוואה היא x+y=0
אחרת המשוואה היא x+!y = 0
נשים לב ש x+y=0 אומר x=y
I x+!y = 0 אומר x!=y

[HAIM KRASNIKER]

אבל מה קורה אם האילוץ הוא

{(1,1)}

בלבד למשל

אז המשוואה

x!=y 

יכולה להיות מסופקת ע"י

0,1

1,0

ואם האילוץ לא מתקיים עדיין המשוואה יכולה להיות מסופקת.

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

?

2009/7/2 itay <itay....@gmail.com>

[itay]

האילוץ הוא פונקציה ולכן חייב להיות פרמוטציה גם ל 0 וגם ל 1, ולכן זה
מתקיים.
כלומר האילוץ צריך להיות או { 1,1 ו 0,0 } או { 0,1 ו 1,0 }

On 2 יולי, 14:57, HAIM KRASNIKER <krash...@gmail.com> wrote:
> אבל מה קורה אם האילוץ הוא{(1,1)}
> בלבד למשל
> אז המשוואה
> x!=y
> יכולה להיות מסופקת ע"י
> 0,1
> 1,0
> ואם האילוץ לא מתקיים עדיין המשוואה יכולה להיות מסופקת.
>
> וזה לא משמר את יחס הקירוב
> ?
>

> 2009/7/2 itay <itay.b.m...@gmail.com>

[itay]

מצאת הסבר לשאלה השניה - לגבי C(1/n)
?

[Noam Schachter]

אני לא משוכנע שהיתה הגבלה לאילוצים סימטריים.

לגבי הסעיף השני.. עדיין לא מצאתי הוכחה.

[Ishay Haviv]

Hi Itay, Noam,

Here is an idea for a solution for cc-07-a-b, question III-b:
We show that SAT belongs to C(1/n) if and only if NP is contained in
BPP, and hence is equivalent to an open question.

First assume that NP is contained in BPP, so SAT has a polynomial
probabilistic algorithm with success probability 2/3. Using
amplification we can get probability of success of, say, 0.9, and this
implies that SAT is in C(1/n).

For the other direction, assume that SAT belongs to C(1/n), so there
exists a polynomial probabilistic Turing machine M that decides SAT
such that if the input is a satisfiable formula then it accepts with
probability at least 3/4+1/n and otherwise accepts with probability at
most 3/4. Our goal is to construct a Turing machine M' for SAT with
success probability of 2/3. The main idea is to run the machine M many
times and to conclude the answer from the answers of M (this is again
an amplification but we should be more careful here). Here are the
details –
Define M' to rum the machine M t times using independent random coins
and to count the number of times that M accepts. Notice that:
- If the instance is YES we expect to have at least (3/4+1/n)t times
that M accepts.
- If the instance is NO we expect to have at most (3/4)t times that M accepts.
So let's say that if the number of times that M accepts is at least
(3/4+1/(2n))t, which is the average between the two numbers above,
then M' accepts and otherwise M' rejects.
It remains to use Chernoff bound to prove that if we take t to be,
say, n^3, then we'll get high probability of success in M'. This
implies that M' runs in polynomial time and hence SAT is in BPP, which
implies that NP is contained in BPP.

Best, Ishay