Complexity Atlas
HE
Source-backed question

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

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

נוסח השאלה

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

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

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

Question 9Page 5Visual reading
View source scan — page 5Source page 5 from נושא 131111 קבוצה 13111101 שנה 2024 סמסטר 1 מועד 2.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