היפר-גרף הוא זוג H=(V,E) כאשר V קבוצת קדקודים ו- E אוסף של תת-קבוצות של V. כל תת-קבוצה כזו…

שאלת רב־ברירהq-b931626bd806

נוסח השאלה

היפר-גרף הוא זוג H=(V,E) כאשר V קבוצת קדקודים ו- E אוסף של תת-קבוצות של V. כל תת-קבוצה כזו נקראת קשת היפר- קשת (היפר-קשתות שונות עשויות בעלות מספר קדקודים שונה). כיסוי קדקודים של H הוא קבוצה $S\subseteq V$ המקיימת שבכל היפר-קשת E יש קדקוד שייך ל- S. מה הטענה (הנכונה) החזקה ביותר שניתן לטעון לגבי הבעיה של מציאת כיסוי קדקודים מינימלי בהיפר-גרף?

אקיים אלגוריתם לבעיה הרץ בזמן פולינומי באורך הקלט ומשיג יחס קירוב O(lg n) .
בקיים אלגוריתם לבעיה הרץ בזמן פולינומי באורך הקלט ומשיג יחס קירוב 2.
גקיים אלגוריתם לבעיה הרץ בזמן פולינומי באורך הקלט ומשיג יחס קירוב 3.
דקיים אלגוריתם לבעיה הרץ בזמן פולינומי באורך הקלט ומשיג יחס קירוב O(√n).
האם קיים אלגוריתם לבעיה הרץ בזמן פולינומי באורך הקלט ומשיג יחס קירוב O(lg n) אז P=NP.
ואם קיים אלגוריתם לבעיה הרץ בזמן פולינומי באורך הקלט ומשיג יחס קירוב O(√n) אז NP=coNP.

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

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

Open full size

נוסח השאלה

Appearances by source document

2023 B · moed A

Related questions from another source type