שיחה:רדוקציה פולינומית

האם המשפט האחרון מדוייק?

בהינתן בעיה ב-NP, יכול להיות שהבעיה היא גם ב-P, ולכן לאחר הרדוקציה היא עדיין תישאר ב-P. או שאני טועה?

תוקן. חגי הלמן 08:54, 18 אוקטובר 2005 (UTC)

סיבוכיות: יחס או הפרש?

ברדוקציה פולינומית, האם מותר לאלגוריתם הפותר את בעיה א' להפעיל את הקופסה השחורה הפותרת את ב' מספר פולינומי של פעמים, או פעם אחת בלבד? עוזי ו. - שיחה 01:32, 9 בספטמבר 2008 (IDT)

אני מקווה שזו היתה שאלה רטורית (אולי רמז לגבי ניסוח הערך?). ברור שמותר מספר פולינומי של פעמים. עוזי ו. - שיחה 21:47, 30 בנובמבר 2009 (IST)

עוזי, אתה מדבר עם עצמך? תומר א. - שיחה 23:50, 4 בדצמבר 2009 (IST)

איחוד

בהתחשב בתוכנו הנוכחי של הערך, רצוי לאחד. יש הצדקה לפיצול כשהערך (המאוחד) יגיע להיקף סביר. עוזי ו. - שיחה 21:53, 30 בנובמבר 2009 (IST)

בהחלט. אני לא בטוח אם יהיה טעם בפיצול גם לאחר מכן. גדי אלכסנדרוביץ' - שיחה 12:05, 1 בדצמבר 2009 (IST)

מה שאני מציע הוא לאחד את הערכים רדוקציה חישובית ורדוקציה פולינומית לערך רדוקציה. לא התרשמתי שיש צורך בשלושה ערכים שונים. רוזבאד - שיחה 21:01, 4 בדצמבר 2009 (IST)

המשך הדיון בשיחה:רדוקציה. תומר א. - שיחה 23:52, 4 בדצמבר 2009 (IST)