תוכן עניינים
8 יחסים: מסלול המילטוני, משפט קוק-לוין, ריצ'רד קארפ, תכנון ליניארי, בעיית הסכומים החלקיים, בעיית העץ של שטיינר, בעיית כיסוי קבוצות, בעיית כיסוי קודקודים.
מסלול המילטוני
מעגל המילטוני על הקשתות של תריסרון מסע הפרש במסלול סגור בתורת הגרפים, מסלול המילטוני הוא מסלול בגרף מכוון או בלתי מכוון העובר בכל צומת בדיוק פעם אחת.
לִרְאוֹת 21 הבעיות ה-NP שלמות של קארפ ומסלול המילטוני
משפט קוק-לוין
משפט קוק-לוין הוא משפט יסודי בתורת הסיבוכיות, הקובע שהבעיה SAT היא NP-שלמה.
לִרְאוֹת 21 הבעיות ה-NP שלמות של קארפ ומשפט קוק-לוין
ריצ'רד קארפ
ריצ'רד מאנינג קארפ (באנגלית: Richard Manning Karp; נולד ב-3 בינואר 1935) הוא מדען מחשב יהודי-אמריקאי, הידוע בעיקר בזכות מחקרו בתאוריה של אלגוריתמים, מחקר שזיכה אותו בפרס טורינג ב-1985 ובפרס הארווי ב-1998.
לִרְאוֹת 21 הבעיות ה-NP שלמות של קארפ וריצ'רד קארפ
תכנון ליניארי
בעיית תכנון ליניארי היא בעיית אופטימיזציה של ביטוי ליניארי תחת אילוצים ליניאריים.
לִרְאוֹת 21 הבעיות ה-NP שלמות של קארפ ותכנון ליניארי
בעיית הסכומים החלקיים
במדעי המחשב, בעיית הסכום החלקי (Subset Sum Problem) היא בעיה חשובה בתורת הסיבוכיות ובקריפטוגרפיה.
לִרְאוֹת 21 הבעיות ה-NP שלמות של קארפ ובעיית הסכומים החלקיים
בעיית העץ של שטיינר
בעיית העץ של שטיינר (באנגלית: Steiner tree problem), שנקראת על שם יאקוב שטיינר, היא מונח המתאר קבוצה של בעיות באופטימיזציה קומבינטורית.
לִרְאוֹת 21 הבעיות ה-NP שלמות של קארפ ובעיית העץ של שטיינר
בעיית כיסוי קבוצות
בעיית כיסוי קבוצות (באנגלית: Set Cover Problem) היא בעיה קלאסית בקומבינטוריקה, מדעי המחשב, אופטימיזציה וסיבוכיות.
לִרְאוֹת 21 הבעיות ה-NP שלמות של קארפ ובעיית כיסוי קבוצות
בעיית כיסוי קודקודים
במדעי המחשב, בעיית כיסוי הקודקודים היא בעיה NP-שלמה בתורת הסיבוכיות.
לִרְאוֹת 21 הבעיות ה-NP שלמות של קארפ ובעיית כיסוי קודקודים