Complexity Atlas
HE
Source-backed question

נתונות 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…

1Exams0Assignments0Lessons1Source documents
שאלת רב־ברירה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. צילום העמוד מצורף למטה כדי שאפשר יהיה לאמת סימון מתמטי וניסוח.

Exact provenance

Appearances by source document

Each card is a genuinely distinct file. Printed versions inside one PDF stay in that card and do not inflate the sitting count.

Exam

2023 B · moed B

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

Question 6Page 4Visual reading

Byte-identical aliases: נושא 131111 קבוצה 13111103 שנה 2023 סמסטר 2 מועד 2.pdf · נושא 131111 קבוצה 13111104 שנה 2023 סמסטר 2 מועד 2.pdf · נושא 131111 קבוצה 13111105 שנה 2023 סמסטר 2 מועד 2.pdf

View source scan — page 4Source page 4 from נושא 131111 קבוצה 13111102 שנה 2023 סמסטר 2 מועד 2.pdf Open full size
Further practice

These are topic and lesson matches, not identical appearances.

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