2006 סמסטר ב' מועד ב'

5 views

Skip to first unread message

unread,

Jun 24, 2010, 1:02:07 PM6/24/10

to Computational Complexity, Spring 2010

כמה מהבעיות הבאות הן NPקשות

Gap-ESAT[9/10,1] .a
Gap-ESAT[9/2006,10/2006] .b
Gap-SAT[9/10,1] .c
Gap-SAT[9/2006,10/2006] .d

התשובה היא 4, כלומר כולם NPקשות.

לא ברור לי למה b,d הן NPקשות.

הרי בהינתן נוסחת CNF, ניתן תמיד לספק לכל הפחות 1/2 מהפסוקיוצ ולכן
בעיות הגאפ אמורות להיות קלות, לא ?
(פשוט מחזירים כן לכל קלט)

מה גם שהיה מבחן שזה היה כתוב בפתרונות שלו.

האם פיספסתי משהו ?

תודה...

unread,

Jun 24, 2010, 1:03:47 PM6/24/10

to computational-comp...@googlegroups.com

זאת טעות,

אני חושב שעידו אמר בשיעור חזרה שבשאלה הזאת נפלה טעות

בתאריך 24 ביוני 2010 20:02, מאת Erez <erezh...@gmail.com>:

Reply all

Reply to author

Forward

0 new messages