שיחה:Sharp-P

תיקון כותרת

גדי, איני מכיר את התבנית הנ"ל, אולם דומני שהיא אינה עובדת במקרה הזה. זה אמור לעשות משהו לכותרת? ירון • שיחה 15:39, 3 באפריל 2007 (IDT)

כן, זה אמור לשנות את מה שכתוב בפס העליון של הדפדפן ל-P#. הייתי שמח לשנות גם את שם הערך עצמו, אבל לא ברור לי איך עושים את זה. גדי אלכסנדרוביץ' 15:43, 3 באפריל 2007 (IDT)

משפט שלא הבנתי

"בפרט, קיימות בעיות ב-NP אשר ידוע להן פתרון יעיל, אך לבעיות המקבילות להן ב-P# לא ידוע פתרון יעיל." - באיזה מובן ידוע להם פתרון יעיל ולמה זה לא מצמצם אותן ל-P? תומר א. - שיחה - _{משנה ויקיפדית} 16:03, 1 בינואר 2010 (IST)

במובן הסטנדרטי, וזה אכן מצמצם אותן ל-P. הסיבה לשימוש ב-NP גם כאן היא בגלל ההקשר שמספק המשפט הקודם. דוגמה: בהינתן פסוק DNF קל לבדוק אם הוא ספיק, אבל אם אפשר יהיה לספור כמה השמות מספקות יש לו, פתרנו את SAT (בהינתן פסוק CNF קח את שלילתו, שבעזרת דה-מורגן תיתן לך פסוק DNF, וכעת ספור אם יש שתיים בחזקת מספר המשתנים השמות מספקות). גדי אלכסנדרוביץ' - שיחה 16:50, 1 בינואר 2010 (IST)

אפשר להוריד את ה-NP בכלל כך שישאר המשפט: בפרט, קיימות בעיות אשר ידוע להן פתרון יעיל, אך לבעיות המקבילות להן ב-P# לא ידוע פתרון יעיל." - הנוסף הנוכחי מעט מבלבל. תומר א. - שיחה - _{משנה ויקיפדית} 17:44, 1 בינואר 2010 (IST)

כמו שאמרתי, ההקשר של המשפט הקודם, שמדבר על בעיות ב-NP בכלל (כולל בעיות NP-שלמות) רלוונטי כאן. באופן כללי כל הפרק הזה מתאר את הקשר בין NP, שבודק קיום פתרונות, ובין P# שסופר אותם. גדי אלכסנדרוביץ' - שיחה 22:13, 1 בינואר 2010 (IST)

ההצעה שלי מתחשבת בהקשר של המשפט הקודם. תומר א. - שיחה - _{משנה ויקיפדית} 22:53, 1 בינואר 2010 (IST)

אני חושב שהנוסח הזה פחות מוצלח אבל אם לדעתך הקודם מבלבל, בבקשה. גדי אלכסנדרוביץ' - שיחה 23:40, 1 בינואר 2010 (IST)

שיניתי לניסוח טיפה יותר מסורבל אבל ששומר על שלום בית. תומר א. - שיחה - _{משנה ויקיפדית} 00:00, 2 בינואר 2010 (IST)

קישור שבור

במהלך מספר ריצות אוטומטיות של הבוט, נמצא שהקישור החיצוני הבא אינו זמין. אנא בדקו אם הקישור אכן שבור, ותקנו אותו או הסירו אותו במקרה זה!

• http://qwiki.stanford.edu/wiki/Complexity_Zoo
  • In Sharp-P on 2013-09-12 22:23:05, 403 Forbidden
  • In מחלקת סיבוכיות on 2013-09-13 03:28:20, 403 Forbidden
  • In סיבוכיות on 2013-09-13 04:32:53, 403 Forbidden
  • In Sharp-P on 2013-09-15 22:06:41, Socket Error: 'Connection timed out'
  • In מחלקת סיבוכיות on 2013-09-16 00:18:59, Socket Error: 'Connection timed out'
  • In Sharp-P on 2013-09-19 22:21:24, Socket Error: 'Connection timed out'
  • In Sharp-P on 2013-09-24 10:58:57, Socket Error: 'Connection timed out'

--Matanyabot - שיחה 13:59, 24 בספטמבר 2013 (IDT)

קישור שבור 2

במהלך מספר ריצות אוטומטיות של הבוט, נמצא שהקישור החיצוני הבא אינו זמין. אנא בדקו אם הקישור אכן שבור, ותקנו אותו או הסירו אותו במקרה זה!

• http://qwiki.stanford.edu/wiki/Complexity_Zoo:Symbols#sharpp
  • In Sharp-P on 2013-09-12 22:23:06, 403 Forbidden
  • In Sharp-P on 2013-09-15 22:06:41, Socket Error: 'Connection timed out'
  • In Sharp-P on 2013-09-19 22:21:24, Socket Error: 'Connection timed out'
  • In Sharp-P on 2013-09-24 10:58:59, Socket Error: 'Connection timed out'

--Matanyabot - שיחה 13:59, 24 בספטמבר 2013 (IDT)