שיחה:שמעון אבן

Hi! I do not speak hebrew. I am brazilian and made the portuguese page of Shimon Even. I included some references that may be helpful. Shalom Uvrahah

לא ברור

מה משמעות המשפט "ההוכחה הראשונה כי בעיה קומבינטורית "טבעית" היא שלמה לPSPACE"? דניאל ב. 16:42, 22 במרץ 2011 (IST)

כשמדברים על בעיה שלמה לא טבעית זאת בד"כ בעיה שנבנתה במיוחד כדי להיות שלמה למחלקה. לדוגמה, יש את השפה שמכילה את כל השלשות (M, x, 1^t) כך ש-M קידוד של מכונת טיורינג שמקבלת את הקלט x תוך שימוש בזיכרון של לכל היותר t. זאת שפה שלמה מאחר ולכל L ב-PSPACE ניתן לבצע אליה רדוקציה על ידי כתיבה של קידוד המכונה שמכריעה את L בזיכרון פולינומי, הקלט והזיכרון המקסימלי הדרוש למכונה באונארית.

בעיה טבעית זאת בעיה שלא נבנתה במיוחד כדי להיות שלמה למחלקה אלא מוגדרת באופן בלתי תלוי בהגדרה של PSPACE. לשיקולכם אם יש נוסח ברור יותר להגיד זאת. ‫87.70.28.204‬ 10:45, 3 במאי 2024 (IDT)

קישור שבור

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

• http://www.cs.technion.ac.il/~even/
  • In שמעון אבן on 2013-06-24 01:09:49, 404 Not Found
  • In שמעון אבן on 2013-07-09 02:14:07, 404 Not Found

--Matanyabot - שיחה 05:14, 9 ביולי 2013 (IDT)