היי יונדב, תודה רבה על הסרטון. מדוע לא ניתן לפשט את הבנייה, ולהגיד שעבור כל משתנה Xi שמופיע ביותר מ3 פסוקיות בנוסחה "פי" אני אחליף אותו במשתנים Xi1, Xi2, ..., Xij ועבור כל שמתנה חדש כזה אני אתן לו את אותה השמה שהיה לXi ב"פי". ואז בכיוון הראשון, ברור שאין משתנה שיופיע ביותר מ3 פסוקיות, וברור שאם "פי" ספיקה גם "פי תאג" ספיקה כי למעשה ההשמה אותה השמה. ובכיוון השני שהצגת כקונטרה פוזיטיב אז אם "פי" לא ספיקה גם "פי טאג" תהיה לא ספיקה כי למעשה יש לה את אותה השמה. כלומר, האם בכך לא ניתן לחסוך את עניין הגרירות? תודה מראש!
היי! הבעייה ברעיון שאתה מציע זה שאי אפשר להגיד ״עבור כל משתנה חדש כזה אני אתן לו את אותה השמה שהיתה למשתנה המקורי ב׳פי׳״, וזה מכמה סיבות. קודם כל, אתה לא יודע במהלך הרדוקצייה מה ההשמה המספקת של ׳פי׳ אז אין לך השמה ביד לעבוד איתה. דבר שני, הפלט שלך אמור להיות נוסחת סי-אן-אף, לא השמה, אז אין משמעות ל״לתת השמה למשתנה״ בהקשר הזה כיוון שאתה צריך לייצר נוסחה. הגרירות שבנינו מטפלות בדיוק בבעיות האלה - הן פסוקיות שאני מוסיף לנוסחה המקורית ששומרות על כך שאם המשתנה המקורי יקבל השמה מסויימת, גם שאר המשתנים המחליפים יהיו חייבים לקבל את אותה השמה על מנת לספק את הנוסחה.
היי יונדב, האם הרדוקציה מחייבת שנקבל פסוק ב-3SAT? (כי לפי מה שהבנתי הרדוקציה מעבירה נוסחא בSAT עם מס' שינויים אבל לא מכריחה שיהיה לי בסופה נוסחא עם פסוקיות של 3 ליטרלים) ואם לא האם זה בעייתי?
היי! זו אכן שאלה טובה מה שאתה מעלה אז קודם כל תשים לב שאנחנו עושים רדוקצייה מ "3 סי-אן-אף" ככה שהנוסחה שאנחנו מתחילים איתה כקלט לרדוקצייה היא כזו שבכל פסוקית יש 3 ליטרלים. כיוון שכך, בפלט הרדוקצייה, כל החלק בנוסחה שהגיע מתוך הנוסחה המקורית, גם אחרי החלפת המשתנים ישמר את התכונה שיש 3 ליטרלים בכל פסוקית. הבעייה היחידה זה הגרירות שאנחנו מוסיפים לנוסחה, שבכל אחת מהן יש שני ליטרלים בפסוקית. לגבי זה יש לי 2 אפשרויות להצדיק למה זה "לא ככ נורא": 1. יכול להיות שההגדרה שהשאלה מכוונת אליה היא שבפסוקית יהיו עד 3 ליטרלים, אבל אפשר שיהיו פחות מ 3. 2. נוכל בכל מקרה לכל פסוקית שיש בה 2 ליטרלים להכפיל את אחד הליטרלים שפשוט יופיע פעמיים בפסוקית עם אותו סימן. זה לא עובר על ההגדרה בשאלה כיוון שההגדרה אוסרת על משתנה אחד להופיע ביותר מ 3 פסוקיות, אבל להופיע פעמיים באותה פסוקית נראה שמותר לו להופיע גם אם הוא מופיע בעוד 2 פסוקיות אחרות.... לדעתי אפשר ככה להצדיק את הבנייה אבל אם נודע לך משהו אחר אשמח אם תכתוב לי
היי יונדב, תודה רבה על הסרטון.
מדוע לא ניתן לפשט את הבנייה, ולהגיד שעבור כל משתנה Xi שמופיע ביותר מ3 פסוקיות בנוסחה "פי" אני אחליף אותו במשתנים Xi1, Xi2, ..., Xij ועבור כל שמתנה חדש כזה אני אתן לו את אותה השמה שהיה לXi ב"פי".
ואז בכיוון הראשון, ברור שאין משתנה שיופיע ביותר מ3 פסוקיות, וברור שאם "פי" ספיקה גם "פי תאג" ספיקה כי למעשה ההשמה אותה השמה.
ובכיוון השני שהצגת כקונטרה פוזיטיב אז אם "פי" לא ספיקה גם "פי טאג" תהיה לא ספיקה כי למעשה יש לה את אותה השמה.
כלומר, האם בכך לא ניתן לחסוך את עניין הגרירות?
תודה מראש!
היי!
הבעייה ברעיון שאתה מציע זה שאי אפשר להגיד ״עבור כל משתנה חדש כזה אני אתן לו את אותה השמה שהיתה למשתנה המקורי ב׳פי׳״, וזה מכמה סיבות. קודם כל, אתה לא יודע במהלך הרדוקצייה מה ההשמה המספקת של ׳פי׳ אז אין לך השמה ביד לעבוד איתה. דבר שני, הפלט שלך אמור להיות נוסחת סי-אן-אף, לא השמה, אז אין משמעות ל״לתת השמה למשתנה״ בהקשר הזה כיוון שאתה צריך לייצר נוסחה. הגרירות שבנינו מטפלות בדיוק בבעיות האלה - הן פסוקיות שאני מוסיף לנוסחה המקורית ששומרות על כך שאם המשתנה המקורי יקבל השמה מסויימת, גם שאר המשתנים המחליפים יהיו חייבים לקבל את אותה השמה על מנת לספק את הנוסחה.
תסתכל ב 13:26
@@Yonadav-bw1vw הבנתי, תודה רבה!
היי יונדב, האם הרדוקציה מחייבת שנקבל פסוק ב-3SAT? (כי לפי מה שהבנתי הרדוקציה מעבירה נוסחא בSAT עם מס' שינויים אבל לא מכריחה שיהיה לי בסופה נוסחא עם פסוקיות של 3 ליטרלים) ואם לא האם זה בעייתי?
היי!
זו אכן שאלה טובה מה שאתה מעלה
אז קודם כל תשים לב שאנחנו עושים רדוקצייה מ "3 סי-אן-אף" ככה שהנוסחה שאנחנו מתחילים איתה כקלט לרדוקצייה היא כזו שבכל פסוקית יש 3 ליטרלים.
כיוון שכך, בפלט הרדוקצייה, כל החלק בנוסחה שהגיע מתוך הנוסחה המקורית, גם אחרי החלפת המשתנים ישמר את התכונה שיש 3 ליטרלים בכל פסוקית.
הבעייה היחידה זה הגרירות שאנחנו מוסיפים לנוסחה, שבכל אחת מהן יש שני ליטרלים בפסוקית.
לגבי זה יש לי 2 אפשרויות להצדיק למה זה "לא ככ נורא":
1. יכול להיות שההגדרה שהשאלה מכוונת אליה היא שבפסוקית יהיו עד 3 ליטרלים, אבל אפשר שיהיו פחות מ 3.
2. נוכל בכל מקרה לכל פסוקית שיש בה 2 ליטרלים להכפיל את אחד הליטרלים שפשוט יופיע פעמיים בפסוקית עם אותו סימן. זה לא עובר על ההגדרה בשאלה כיוון שההגדרה אוסרת על משתנה אחד להופיע ביותר מ 3 פסוקיות, אבל להופיע פעמיים באותה פסוקית נראה שמותר לו להופיע גם אם הוא מופיע בעוד 2 פסוקיות אחרות....
לדעתי אפשר ככה להצדיק את הבנייה אבל אם נודע לך משהו אחר אשמח אם תכתוב לי
@@Yonadav-bw1vw הבנתי, תודה רבה על הסרטון והתשובה המפורטת!