בסעיף א', היה אפשר להגדיר את S1 להיות שפת הזוגות כאשר כל איבר הוא נוסחא כלשהי, כלומר (a,b) כאשר a,b נוסחאות כלשהן. וS2 להיות שפת הזוגות כאשר האיבר הראשון הוא מSAT משלים והאיבר השני הוא מSAT. בניה כזו היא חוקית?
@@אליטוטח יש מצב גדול שמבחינת ה"חיסור שפות" יצא לך בסוף בסדר, הבעייה בגישה הזו היא שלא תצליח להראות ש "אס שתיים" שייכת ל "אן-פי", כיוון שאתה קובע שהאיבר הראשון הוא מ סאט משלים. אתה בעצם צריך להראות מוודא פולינומי מסוג "אן-פי" שיצליח לוודא עבור האיבר הראשון האם הוא נוסחה לא ספיקה, וזה כמובן שקול לשאלה הפתוחה "אן-פי שווה קו אן פי".
תודה רבה יונדב! אין עליך
🏅🏅
לדעתי גם אם p=np אז הגרירה נכונה באופן ריק
בסעיף א', היה אפשר להגדיר את S1 להיות שפת הזוגות כאשר כל איבר הוא נוסחא כלשהי, כלומר (a,b) כאשר a,b נוסחאות כלשהן.
וS2 להיות שפת הזוגות כאשר האיבר הראשון הוא מSAT משלים והאיבר השני הוא מSAT.
בניה כזו היא חוקית?
@@אליטוטח יש מצב גדול שמבחינת ה"חיסור שפות" יצא לך בסוף בסדר, הבעייה בגישה הזו היא שלא תצליח להראות ש "אס שתיים" שייכת ל "אן-פי", כיוון שאתה קובע שהאיבר הראשון הוא מ סאט משלים. אתה בעצם צריך להראות מוודא פולינומי מסוג "אן-פי" שיצליח לוודא עבור האיבר הראשון האם הוא נוסחה לא ספיקה, וזה כמובן שקול לשאלה הפתוחה "אן-פי שווה קו אן פי".