cc07b-c מבחן 2007 סמסטר ב' מועד ג'

[Ran Zvilik]

שאלה 2ב':

נגדיר את בעיית ההבטחה PCUT:
קלט: גרף לא מכוון G עם משקולות חיוביות על הקשתות, ומספר t.
Yes: יש בגרף בדיוק חתך אחד בדיוק שמשקלו לפחות t.
No: כל חתך בגרף הוא במשקל < t.

(תזכורת: משקל החתך הוא סכום משקולות הקשתות בין S לבין V\S).

הראו שאם PCUT שייכת ל-P אז MaxCut שייכת ל-BPP.

רעיונות למישהו? :/

[Tom Teman]

We can deduce MAX-2-SAT to PCUT.

Given a 2SAT formula, we convert the variables to vertices and the literals to edges (i.e - X OR Y will be converted to 2 vertices connected by an edge). It's easy to see that the max cut finds the maximal satisfiability: both vertices groups signify the variables that should be assigned T and F, doesn't matter which.

Actually, we need to find the max-cut - we'll simply run PCUT with different k values - from i to n^2, and find the maximal k. 

This means that MAX-2-SAT is in P, which means all that itai said.

2010/6/24 Einat Kreiczer <eina...@gmail.com>

ואיך מראים את זה?

בתאריך 24 ביוני 2010 19:25, מאת itai rosenblatt dong...@gmail.com:

> נראה לי שפשוט צריך להראות שאם הבעיה היא ב
> P
> אז
> NP=P
> ואז ההיררכיה הפולינומית קורסת
> ולכן
> BPP=P=NP....
> ולכן גם
> MAX-CUT is in BPP
>
> 2010/6/24 Ran Zvilik <rzv...@gmail.com>