תוצאות החיפוש

...צור המילה ה[[אנגלית]] Approximable, ניתן לקירוב) היא [[מחלקת סיבוכיות]] של בעיות אופטימיזציה להן ניתן למצוא פתרון מקורב על ידי [[אלגוריתם קירוב]] בסיבוכיות ...בזמן פולינומי אלא אם כן [[בעיית P=NP|P=NP]], כלומר - לכל הבעיות השייכות ל-NP קיים פתרון פולינומי. ...

...יה]] חשובה, בה יש לארוז חפצים במספר מינימלי של דליים. הבעיה היא [[NP-קשיות|NP-קשה]]. ...היא NP-שלמה. הבעיה היא גם NP קשה חזקה, כלומר גם קבלת הקלט בכתיב אונארי היא NP קשה (בניגוד ל[[בעיית תרמיל הגב]] למשל). ...

...ות שעבורן קיים מוודא בזמן פולינומי). בעיה זו משמשת בהוכחות רבות עבור בעיות NP-שלמות אחרות. ...ורה נורמלית קוניונקטיבית|בצורה הנורמלית הקוניונקטיבית]] (CNF), הבעיה תישאר NP-קשה. לכן, בשל נוחות העבודה עם נוסחאות בצורת CNF, מקובל לנסח את הבעיה רק עבו ...

...את אוסף בעיות הספירה הקשורות לבעיות ההכרעה השייכות למחלקה [[NP (סיבוכיות)|NP]]. בעיות רבות במדעי המחשב מנוסחות כ'''בעיות הכרעה''' - בעיות שהתשובה להן היא "כן" או "לא". למשל, האם ניתן לבחור [[קבוצה (מתמטיקה)|תת קבו ...

...נקראת [[APX]], ניתן להוכיח שיש בעיות שאין להם אלגוריתם קירוב אלא אם כן [[P=NP]]. בעיה זו היא [[NP-קשה]], אולם ניתן לקרב אותה באופן הבא (האלגוריתם של קריסטופידס{{הערה|1=Nicos ...

במובנה הכללי ביותר, משמשת הרדוקציה על מנת להוכיח כי בעיות מסוימות הן [[כריעות]] (בעלות אלגוריתם המכריע אותן) ב[[מודל חישובי]] כלשהו ב ...יעיל שלהן יגרור פתרון יעיל של כל המחלקה. בעיות אלו נקראות [[בעיה NP-קשה|NP-קשות]]. ...

...וש מקומי''' הוא טכניקה [[היוריסטיקה|היוריסטית]]-למחצה לפתרון [[בעיית מיטוב|בעיות מיטוב]]. השיטה כוללת שיפור הדרגתי של פתרון נתון, על ידי בחירת פתרונות קרובי ...ן סביר, מה שגורם לכך שפעמים רבות בוחרים בשיטה כזו עבור בעיות [[NP-קשיות|NP קשות]].{{הערה|[http://www.designofapproxalgs.com/book.pdf the desine of approxim ...

...תמטיקה]], שהכריז על פרס בסך מיליון דולר שיוענק למי שיפתור את הבעיה{{הערה|7 בעיות המילניום, [http://www.claymath.org/millennium-problems/ אתר מכון קליי למתמט ...np-hard.svg|שמאל|ממוזער|400px|מחלקת NP בהנחה ש-P = NP (מימין) ובהנחה ש-P ≠ NP (משמאל)]] ...

...ath>k>2</math>, ההכרעה האם <math>\chi(G)=k</math> היא בעיה [[NP_(סיבוכיות)|NP שלמה]]. לגרף יש מספר כרומטי 2 [[אם ורק אם]] אין בו מעגל באורך אי זוגי. ...ת צביעת גרפים מופיעה בבעיות מגוונות כשאלגוריתמים בתחום זה שימושים בהקשר של בעיות של תזמון משימות, הקצאת [[אוגר (מחשבים)|אוגרים]], זיהוי תבניות ופתרון תשבצי ...

הבעיה נכללת במחלקת הסיבוכיות [[NP-קשיות]], והיא אחת מהבעיות המרכזיות בתחום [[אופטימיזציה (מתמטיקה)|האופטימיזצ בשנת 1972 [[ריצ'רד קארפ]] הראה שמסלול המילטון היא בעיה השייכת לקטגוריה [[NP-שלמה]], ובכך סיפק הסבר מתמטי לקושי החישובי במציאת מסלול אופטימלי. ...

...עו מועמדים רבים לפונקציה חד-כיוונית עם דלת צונחת. קיים מגוון בעיות מתמטיות קשות לא בהכרח מ[[תורת המספרים]] שאפשר לבסס עליהן פונקציה חד-כיוונית. לדוגמה בעיי *פונקציות מבוססות בעיות מתורת הסריגים. ...

...ימות של [[בעיית התרמיל]] קשות לפתרון במקרה הממוצע לפחות כמו המקרה הגרוע של בעיות הסריג. עניין נוסף עלה בעקבות גילוי אלגוריתם [[LLL]] על ידי Lenstra, Lenstra ...עיל]] שיכול לבצע קירוב עד כדי <math>2^{c/\text{loglog}n}</math> אלא אם [[P=NP]]. הממצאים הללו אומתו אחר מחקרים שנעשו בתחום זה על ידי רבים. ...

במדעי המחשב חיפוש ממצה מתאר טכניקות גנריות לפתרון בעיות מתמטיות המסתמכות על מיפוי שיטתי של כל הפתרונות האפשריים ובדיקה האם נמצא בינ ...fram.com/ExhaustiveSearch.html Exhaustive Search]}}, אלא אם כן יתברר ש-[[P=NP]]. ...

...-מעריכי. משמעות הדבר שפרוטוקול דיפי-הלמן, RSA וכן כל נגזרותיהם המסתמכים על בעיות דומות יצאו מכלל שימוש<ref name=":0" />. ...אינו מתאים לשימוש כללי ואינו רלוונטי לקריפטואנליזה, הוא מתאים בעיקר לפתרון בעיות מיוחדות בתחום [[אופטימיזציה (מתמטיקה)|אופטימיזציה]], [[ביואינפורמטיקה]] וכד ...

...שר <math>s</math> הוא הסינדרום. הוכח על ידי ברלקמפ, מקאליס וטילבורג שהבעיה NP-קשה{{הערה|Berlekamp, E.R., R.J. McEliece, and H.C. van Tilborg (1978). “On ...

..., וניתן להוכיח עליה טענות בקלות רבה יותר; תחת הגדרה זו ניתן להוכיח קיום של בעיות שלמות וקיום של פרוטוקולים קצרים מאוד. ההגדרה האחרונה, החלשה ביותר, היא על פ ...כל בעיית NP-שלמה ניתנת לשימוש כבסיס למערכת הוכחה באפס ידיעה, כמו גם בעיות קשות אחרות, כמו בעיית ה[[פירוק לגורמים של מספר שלם]]. ...

...במדעי המחשב (בפרט, תשובה חיובית לשאלה זו תהווה הוכחה לכך ש-[[P=NP|P שונה מ-NP]], מה שישים קץ לשאלה הפתוחה המרכזית במדעי המחשב). ...ים הנפוצים בימינו ובכך להוציאם מכלל שימוש. עם זאת קיימים אלגוריתמים לפתרון בעיות יסודיות אלו ב[[סיבוכיות זמן]] היעילים במידה ניכרת מ[[כוח גס]]. מסיבה זו רצו ...

...ת [[מתמטיקה|מתמטיות]] קשות שלא ידוע אם קיים עבורן פתרון ב[[זמן פולינומי]]. בעיות אלו מאפשרות יישום [[פונקציה חד-כיוונית#פונקציה חד-כיוונית עם דלת צונחת|פונק ...ח תשליך על פתרון [[בעיה מתמטית]] ארוכת שנים מ[[תורת הסיבוכיות]] שנקראת [[P=NP]], מה שלא סביר כלל שיקרה. לכן הדרך המקובלת להתייחס לפונקציה חד-כיוונית היא ...

...התקדמות הטכנולוגית (בעיקר בתחום פירוק לגורמים) ופגיעותן לאלגוריתמים לפתרון בעיות אלה, המפתחות חייבים להיות בסדר גודל של אלפי ספרות בינאריות. עובדה המאפילה ע ...-מעריכיים]] לפתרון הבעיות המנויות, אך האלגוריתם היעיל ביותר (הידוע) לפתרון בעיות (במחשב קלאסי) אלו עבור עקומים אליפטיים הוא בעל זמן ריצה מעריכי. עקב כך, מפת ...