מפת הסיבוכיות
EN
שאלה מבוססת מקור

נסתכל על 3 הבעיות הבאות: בעיית ההכרעה של SAT: בהינתן נוסחה בוליאנית בצורת CNF - האם הנוסחה ספיקה. בעיית החיפוש…

1בחינות0מטלות0שיעורים1מסמכי מקור
שאלת רב־ברירהq-1bdd4b2c2a83

נוסח השאלה

נסתכל על 3 הבעיות הבאות: בעיית ההכרעה של SAT: בהינתן נוסחה בוליאנית בצורת CNF - האם הנוסחה ספיקה. בעיית החיפוש של SAT: בהינתן נוסחה בוליאנית בצורת CNF - למצוא השמה מספקת אם יש כזו או "לא" אם אין לנוסחה השמה מספקת. בעיית האופטימיזציה של SAT: בהינתן נוסחה בוליאנית בצורת CNF - מה המספר המקסימלי של פסוקיות שניתן לספק (על ידי איזושהי השמה). מה הטענה הנכונה (כאשר בכל המקרים הכוונה במילה "פתרון" היא על ידי מכונת טיורינג דטרמיניסטית)?
  1. אכל הטענות ב' ג' ד' הן נכונות.
  2. באם ניתן להכריע את בעיית SAT בזמן פולינומיאלי אז ניתן לפתור את בעיית החיפוש של SAT בזמן פולינומיאלי.
  3. גאם ניתן לפתור את בעיית החיפוש של SAT בזמן פולינומיאלי אז ניתן להכריע את SAT בזמן פולינומיאלי.
  4. דאם ניתן לפתור את בעיית האופטימיזציה של SAT בזמן פולינומיאלי אז ניתן להכריע את SAT בזמן פולינומיאלי.
  5. השתיים מבין הטענות ב' ג' ד' הן נכונות.
  6. ואף אחת מהטענות ב' ג' ד' אינה נכונה.

תמלול ראשון מתוך עמוד המקור ב־tools/summary/.work. צילום העמוד מצורף למטה כדי שאפשר יהיה לאמת סימון מתמטי וניסוח.

ייחוס מדויק

מופעים לפי מסמך מקור

כל כרטיס הוא קובץ שונה באמת. גרסאות או שאלונים כפולים באותו PDF מוצגים בתוך אותו כרטיס ואינם מגדילים את מספר המועדים.

בחינה

2024 א׳ · מועד ב׳

נושא 131111 קבוצה 13111101 שנה 2024 סמסטר 1 מועד 2.pdf

שאלה 9עמוד 5קריאה חזותית
הצגת צילום המקור — עמוד 5עמוד מקור 5 מתוך נושא 131111 קבוצה 13111101 שנה 2024 סמסטר 1 מועד 2.pdf פתיחה בגודל מלא
תרגול המשך

אלו התאמות לפי נושא ושיעור — לא מופעים זהים של אותה שאלה.

מטלהעבור כל אחת ממחלקות הסיבוכיות הבאות, קבעו אם היא מכילה את NP, מוכלת ב-NP, ושווה ל-NP - אם הדבר ידוע. הוכיחו את קביעותיכם. כאשר קובעים ששתי מחלקות שוות…דומה בנושא — לא כפילותמטלהעבור כל אחת ממחלקות הסיבוכיות שלהלן, קבעו האם היא מכילה את המחלקה NP, האם NP מוכלת בה, והאם היא שווה לה, אם ידוע. אחרת הוכיחו כי השאלה שקולה לשאלה פתו…דומה בנושא — לא כפילותמטלהיהי [0,1]. נגדיר את מחלקות הסיבוכיות הבאות: - C 1 היא מחלקת כל השפות שעבורן קיימת מכונת טיורינג הסתברותית M הרצה בזמן פולינומי בגודל הקלט, כך שלכל x *…דומה בנושא — לא כפילותמטלהיהי [0,1]. נגדיר: - C 1 היא מחלקת השפות A שעבורן קיימת מכונת טיורינג הסתברותית M הרצה בזמן פולינומי, כך שלכל x: - אם x A, אז [M accepts x] ; - אם x A,…דומה בנושא — לא כפילותמטלה1. הוכיחו כי RP NP. 2. הוכיחו כי BPP PSPACE. 3. הוכיחו כי מחלקת הסיבוכיות RP סגורה לחיתוך, כלומר שאם A,B RP אז A B RP. 4. זהו את מחלקות הסיבוכיות שלהל…דומה בנושא — לא כפילותמטלהעבור כל אחת מן המחלקות הבאות קבעו אם היא מכילה את NP, אם היא מוכלת ב-NP, ואם היא שווה ל-NP, ככל שידוע; אחרת הוכיחו כי השאלה שקולה לשאלה פתוחה. 1. C 1:…דומה בנושא — לא כפילות

וריאציות קרובות — לא כפילויות