Complexity Atlas
HE
Source-backed question

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

1Exams0Assignments0Lessons1Source documents
שאלת רב־ברירהq-0c98c8761251

נוסח השאלה

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

תמלול ראשון מתוך עמוד המקור ב־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

2024 A · moed A

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

Question 9Page 7Visual reading
View source scan — page 7Source page 7 from נושא 131111 קבוצה 13111101 שנה 2024 סמסטר 1 מועד 1.pdf Open full size
Further practice

These are topic and lesson matches, not identical appearances.

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

Near variants — not duplicates