Complexity Atlas
HE
Source-backed question

הוכיחו כי מחלקת הסיבוכיות DTime(n 10) אינה סגורה לרדוקציות זמן פולינומי. **רמז:** השתמשו במשפט ההיררכיה בזמן ו…

0Exams1Assignments0Lessons1Source documents
שאלה פתוחהq-b362f63aa365

נוסח השאלה

הוכיחו כי מחלקת הסיבוכיות DTime(n10)DTime(n^{10}) אינה סגורה לרדוקציות זמן פולינומי.

רמז: השתמשו במשפט ההיררכיה בזמן ובמשפט הבא שהוכחנו בשיעור: לכל שתי שפות A,BA,B, אם B∈PB\in P וגם AA אינה טריוויאלית, אז A≤pBA\le_p B.

נוסח מטלה שנבדק אנושית.

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.

Assignment

2026 A

2026א_03_תרגיל_3.md

Question 2Page 1Human reviewed
Further practice

These are topic and lesson matches, not identical appearances.

Lesson1. בפברואר 2025, פירסם ריאן ויליאמס מאוניברסיטת MIT תוצאה פורצת דרך לפיה לכל פונקציה f: ℕ ℕ המקיימת n f(n) לכל n, מתקיים DTime(f) ⊆ DSpace(√(f ⋅ log 2…Topically related — not a duplicateExamמבין המחלקות הבאות, מה המחלקה הקטנה ביותר ביחס להכלה שידוע לגביה שהיא סגורה תחת רדוקציות זמן פולינומיאלי.Topically related — not a duplicateExamשפה A ניתנת להכרעה ע"י מכונת טיורינג דטרמיניסטית שמשתמשת במקום O(n 2) לקלט באורך n. שפה B ניתנת לרדוקציה לשפה A ע"י מ"ט דטרמיניסטית בזמן O(n 3) לקלט ב…Topically related — not a duplicateExamשפה A ניתנת להכרעה ע"י מכונת טיורינג עם 2 5 סרטים בזמן O(n 2) לקלט באורך n. שפה B ניתנת לרדוקציה משפה A ע"י מכונת טיורינג עם 2 10 סרטים בזמן O(n 3) לק…Topically related — not a duplicateExamעבור אילו מהטענות הבאות ידוע כי היא שקולה לטענה P = NP?Topically related — not a duplicateExamנתונות מחלקות הסיבוכיות הבאות. I. המחלקה C 1 היא מחלקת כל השפות A Σ* עבור קיימת מכונת טיורינג אי-דטרמיניסטית M וקיימים c 1 כך שלכל x Σ*, אם x A אז קיי…Topically related — not a duplicate

Near variants — not duplicates