משהו יודע למה זה ב NPC ולא ב P?
Oza
קלט: נוסחת Exactly-2-CNF (כלומר כל הסגר ב- מכיל 2 ליטרלים של
משתנים שונים) ומספר טבעי k.
שאלה: האם קיימת השמה שמספקת את , כך שלכל היותר k משתנים מקבלים ערך
T ?
מהי המחלקה הקטנה ביותר שאליה שייכת הבעיה, אם כל הליטרלים הם משתנים
(ולא שלילות של משתנים)?
א. PSPACE
ב. NPC
ג. NP
ד. co-NP
ה. P
Einat Kreiczer
1.
כנ"ל, כאשר בכל הסגר, ליטרל אחד
הוא משתנה והשני הוא שלילה של משתנה.
א. PSPACE
ב. NPC
ג. NP
ד. co-NP
ה. P
התשובה היא P
משהו יכול להסביר את ההבדל
תודה :)
Ran Zvilik
On Jun 23, 10:29 pm, Einat Kreiczer <einat...@gmail.com> wrote:
> ושאלה אחר כך
>
> 1. כנ"ל, כאשר בכל הסגר, ליטרל אחד הוא משתנה והשני הוא שלילה של משתנה.
>
> א. PSPACE
>
> ב. NPC
>
> ג. NP
>
> ד. co-NP
>
> ה. P
>
> התשובה היא P
>
> משהו יכול להסביר את ההבדל
>
> תודה :)
>
> בתאריך 23 ביוני 2010 22:28, מאת Oza <einat...@gmail.com>:
Yigal Shenkman
VC
x1---x2
צמתים שמחוברים בקשת
עובר ל
(x1 or x2)
הרעיון הוא שצריך למצוא קבוצת צמתים בגודל
K
שנמצאות בכל ההסגרים.
Yigal Shenkman
false
כלומר נחזיר תמיד 'כן'
On Jun 23, 10:29 pm, Einat Kreiczer <einat...@gmail.com> wrote:
> ושאלה אחר כך
>
> 1. כנ"ל, כאשר בכל הסגר, ליטרל אחד הוא משתנה והשני הוא שלילה של משתנה.
>
> א. PSPACE
>
> ב. NPC
>
> ג. NP
>
> ד. co-NP
>
> ה. P
>
> התשובה היא P
>
> משהו יכול להסביר את ההבדל
>
> תודה :)
>
> בתאריך 23 ביוני 2010 22:28, מאת Oza <einat...@gmail.com>:
dannyvai
On Jun 24, 12:59 pm, Eyal Dushkin <eyal...@gmail.com> wrote:
> אין צורך לחזור על דבריי המתרגל יגאל.
> 0
> > > > ה. P- Hide quoted text -
>
> - Show quoted text -
itai rosenblatt
Haim Nachmias
תחת האילוץ.
On Jun 24, 1:49 pm, itai rosenblatt <dongo...@gmail.com> wrote:
> אפשר פשוט לתת לכל המשתנים את הערך
> FALSE
> וכך מספקים את כל הפסוקיות
>
> 2010/6/24 Ran Zvilik <rzvi...@gmail.com>
Eyal Dushkin
הפסוקית.
Yigal Shenkman
FALSE
לכל המשתנים.