חישוביות 2024 תרגיל 3 שאלה 4 - מחלקת כל השפות שהן חיסור שתי שפות מ NP
Рет қаралды 677
Күн бұрын
@user-wh9cn4ei5q Ай бұрын
🏅🏅
@user-gt1pw2oj5z 2 ай бұрын
לדעתי גם אם p=np אז הגרירה נכונה באופן ריק
@MissOrka14 2 ай бұрын
תודה רבה יונדב! אין עליך
@user-dv9iz5qe6p 2 ай бұрын
בסעיף א', היה אפשר להגדיר את S1 להיות שפת הזוגות כאשר כל איבר הוא נוסחא כלשהי, כלומר (a,b) כאשר a,b נוסחאות כלשהן. וS2 להיות שפת הזוגות כאשר האיבר הראשון הוא מSAT משלים והאיבר השני הוא מSAT. בניה כזו היא חוקית?
@Yonadav-bw1vw 2 ай бұрын
@@user-dv9iz5qe6p יש מצב גדול שמבחינת ה"חיסור שפות" יצא לך בסוף בסדר, הבעייה בגישה הזו היא שלא תצליח להראות ש "אס שתיים" שייכת ל "אן-פי", כיוון שאתה קובע שהאיבר הראשון הוא מ סאט משלים. אתה בעצם צריך להראות מוודא פולינומי מסוג "אן-פי" שיצליח לוודא עבור האיבר הראשון האם הוא נוסחה לא ספיקה, וזה כמובן שקול לשאלה הפתוחה "אן-פי שווה קו אן פי".
Фани Хани
Рет қаралды 3,4 МЛН
Фани Хани
Рет қаралды 2,8 МЛН
Dr. Mordechai Kedar - Hebrew
Рет қаралды 386 М.
TOV אקטואליה יהודית
Рет қаралды 104 М.
Benjamin Netanyahu - בנימין נתניהו
Рет қаралды 101 М.
הטכניון - מכון טכנולוגי לישראל
Рет қаралды 341 М.
Фани Хани
Рет қаралды 3,4 МЛН