Complexity Atlas
HE
Source-backed question

אילו מהטענות הבאות היא הטענה החזקה ביותר בוודעה נכונה?

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

נוסח השאלה

אילו מהטענות הבאות היא הטענה החזקה ביותר בוודעה נכונה?
  1. אאף אחד מהסעיפים ב' ג' ד' ה' אינו ידוע נכון.
  2. בNP≠P.
  3. גNP≠NPSPACE.
  4. דNP≠EXP.
  5. הNP שונה ממחלקת השפות שקיימת עבורן טיורינג אי-דטרמינסטית A∈Σ* וכך שלכל M מכונת M וכך שלכל x∈Σ* אם x∈A אז
  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

2023 B · moed A

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

Question 13Page 11Visual reading

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

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

These are topic and lesson matches, not identical appearances.

Assignmentבכל סעיף מוצגות טענה ואלגוריתם. קבעו אם האלגוריתם מגדיר רדוקציית זמן פולינומי המוכיחה את הטענה, והוכיחו את קביעתכם. נשתמש בהגדרות: - נוסחת CNF ספיקה ב…Topically related — not a duplicateAssignmentלכל טענה קבעו האם היא נכונה, אינה נכונה, או שקולה לשאלה פתוחה, והוכיחו את קביעתכם. השפה SAT-UNSAT היא שפת הזוגות ( 1, 2) של נוסחאות בוליאניות מצורת CN…Topically related — not a duplicateAssignmentיהיו k N ו-A \0, ,k\. נגדיר את הבעיה kSAT A: קלט: נוסחה בצורת k-CNF. שאלה: האם קיימת השמה כך שבכל פסוקית מספר הליטרלים המקבלים אמת שייך ל-A? לדוגמה, ב…Topically related — not a duplicateAssignmentיהי [0,1]. נגדיר את מחלקות הסיבוכיות הבאות: - C 1 היא מחלקת כל השפות שעבורן קיימת מכונת טיורינג הסתברותית M הרצה בזמן פולינומי בגודל הקלט, כך שלכל x *…Topically related — not a duplicateAssignmentלכל אחת מבעיות ההכרעה שלהלן קבעו מהי מחלקת הסיבוכיות הקטנה ביותר ביחס להכלה שאליה ידוע שהיא שייכת מבין המחלקות P,NP,coNP,EXP. הוכיחו את קביעותיכם. 1.…Topically related — not a duplicateAssignmentיהי [0,1]. נגדיר: - C 1 היא מחלקת השפות A שעבורן קיימת מכונת טיורינג הסתברותית M הרצה בזמן פולינומי, כך שלכל x: - אם x A, אז [M accepts x] ; - אם x A,…Topically related — not a duplicate

Near variants — not duplicates