רוטר - שאלה לגבי NP ו NP COMPLETE

יומן פעילות	לוח שנה	מבזקי חדשות	תקנון	RSS	כותרות	כותרות לפי תגובה	ניקוי קוקיז	IP	להורדת אפליקציה
eBay	AliExpress	GearBest	Amazon	Booking	Kiwi	SkyScanner	Trip Advisor

"שאלה לגבי NP ו NP COMPLETE"

גירסת הדפסה

קבוצות דיון פיתוח, תיכנות ובניית אתרים נושא #10589	מנהל סגן המנהל מפקח Winner צל"ש מומחה

אשכול מספר 10589

-KINGMAN-

חבר מתאריך 13.4.03
7284 הודעות, 2 פידבק

23:29 30.01.12

שאלה לגבי NP ו NP COMPLETE

אז ככה מצאתי בויקיפדיה אבל זה קצת לא ברור לי ואשמח עם מישהו יוכל להסביר לי את זה במילים שלו
רציתי לשאול
מהי בעית NP ?
מהי בעיית NP COMLETE ?
מה החשיבות של בעיות NP שלמות? ומה יקרה אם נצליח לפתור בעיית NP שלמה ביעילות? ואיך זה משפיע על בעיות אחרות ב- NP ?
אשמח להסבר תודה רבה לעוזרים

שתף

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

האשכול	מחבר	תאריך כתיבה	מספר
ממה שאני זוכר	VeNom	31.01.12 00:29	1
תודה רבה אחי!! יש לי עוד שאלה קטנה בנושא	-KINGMAN-	31.01.12 12:35	2

VeNom

חבר מתאריך 7.6.02
7922 הודעות, 1 פידבק

00:29 31.01.12

1. ממה שאני זוכר
בתגובה להודעה מספר 0

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

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

-KINGMAN-

חבר מתאריך 13.4.03
7284 הודעות, 2 פידבק

12:35 31.01.12

2. תודה רבה אחי!! יש לי עוד שאלה קטנה בנושא
בתגובה להודעה מספר 0

ערכתי לאחרונה בתאריך 31.01.12 בשעה 12:42 בברכה, -KINGMAN-

בעיית 8 המלכות היא נחשבת בעיית ב- NP או NP שלמה? או אפילו בעיה כמו סודוקו זה NP או NP שלמה? ונגיד החלק "הקל" שניתן לעשות בסודוקו בזמן פולינמיאלי זה רק ההצבה הראשונית נכון?

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד