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

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

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

נוסח השאלה

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

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

ייחוס מדויק

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

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

בחינה

2023 ב׳ · מועד א׳

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

שאלה 13עמוד 11קריאה חזותית

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

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

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

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

וריאציות קרובות — לא כפילויות