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

נתונות 4 טענות הבאות. A. NP BPP(1/n,1). B. NP BPP(1-1/n,1). C. NP=BPP(1/n,1). D. NP=BPP(1-1/n,1). אם ידוע כי N…

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

נוסח השאלה

נתונות 4 טענות הבאות.A.NP⊆BPP(1/n,1).B.NP⊆BPP(1−1/n,1).C.NP=BPP(1/n,1).D.NP=BPP(1−1/n,1). A. NP\subseteq BPP(1/n,1). B. NP\subseteq BPP(1-1/n,1). C. NP=BPP(1/n,1). D. NP=BPP(1-1/n,1). אם ידוע כי NP⊆BPPNP\subseteq BPP, אילו מהטענות A,B,C,D שהובאו לעיל ניתן להסיק?

  1. אכל ארבע הטענות A,B,C,D נכונות.
  2. בלא ניתן להסיק נכונות אף אחת מהטענות A,B,C,D מסיבה אחרת המצוינה בהסיבה מהתשובה ו'.
  3. גאחת מהטענות A,B,C,D נכונה.
  4. דשתיים מהטענות A,B,C,D נכונות.
  5. השלוש מהטענות A,B,C,D נכונות.
  6. ולא ניתן להסיק נכונות אף אחת מהטענות A,B,C,D כי BPP מחלקה הסתברותית שעוד ש- NP מחלקה

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

ייחוס מדויק

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

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

בחינה

2023 ב׳ · מועד ב׳

נושא 131111 קבוצה 13111102 שנה 2023 סמסטר 2 מועד 2.pdf

שאלה 6עמוד 4קריאה חזותית

עותקים זהים של אותו מסמך: נושא 131111 קבוצה 13111103 שנה 2023 סמסטר 2 מועד 2.pdf · נושא 131111 קבוצה 13111104 שנה 2023 סמסטר 2 מועד 2.pdf · נושא 131111 קבוצה 13111105 שנה 2023 סמסטר 2 מועד 2.pdf

הצגת צילום המקור — עמוד 4עמוד מקור 4 מתוך נושא 131111 קבוצה 13111102 שנה 2023 סמסטר 2 מועד 2.pdf פתיחה בגודל מלא
תרגול המשך

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

מטלה1. הוכיחו כי RP NP. 2. הוכיחו כי BPP PSPACE. 3. הוכיחו כי מחלקת הסיבוכיות RP סגורה לחיתוך, כלומר שאם A,B RP אז A B RP. 4. זהו את מחלקות הסיבוכיות שלהל…דומה בנושא — לא כפילותמטלההוכיחו את הטענות הבאות: 1. BPP PSPACE. 2. לכל A,B RP מתקיים A B RP. 3. לכל A,B BPP מתקיים A B BPP. 4. RP NP BPP.דומה בנושא — לא כפילותמטלההוכיחו את הטענות הבאות: 1. BPP PSPACE. 2. RP סגורה לאיחוד. 3. BPP סגורה לחיתוך. 4. RP NP BPP. 5. BPP=BPP(5/6,5/6).דומה בנושא — לא כפילותמטלה1. תהא נוסחה בוליאנית מצורת 5CNF בעלת m הסגרים, שבכל אחד מהם מופיעים חמישה משתנים שונים, בחיוב או בשלילה. 1. חשבו את תוחלת מספר ההסגרים המסופקים בנוסח…דומה בנושא — לא כפילותמטלהלכל טענה קבעו האם היא נכונה, אינה נכונה, או שקולה לשאלה פתוחה, והוכיחו את קביעתכם. השפה SAT-UNSAT היא שפת הזוגות ( 1, 2) של נוסחאות בוליאניות מצורת CN…דומה בנושא — לא כפילותמטלהיהי [0,1]. נגדיר את מחלקות הסיבוכיות הבאות: - C 1 היא מחלקת כל השפות שעבורן קיימת מכונת טיורינג הסתברותית M הרצה בזמן פולינומי בגודל הקלט, כך שלכל x *…דומה בנושא — לא כפילות