על P=NP מעל חבורות אבליות – סוף דבר

בשני הפוסטים האחרונים אני מכין את הקרקע לקראת הוכחה ש-$latex \mbox{P}\ne\mbox{NP}$ במודלים חישוביים שהם מעל חבורות אבליות אינסופיות. בפוסט הראשון הצגתי את הרעיון שמאחורי מודל חישובי שכזה והצגתי הוכחה לכך שעבור המקרה הקונקרטי של $latex G=\mathbb{Z}$ אנחנו אכן מקבלים ש-$latex … להמשיך לקרוא

על על-מסננים ועל-מכפלות

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

על P=NP מעל חבורות אבליות – מבוא שלם

בואו נוכיח ש-$latex \mbox{P}\ne\mbox{NP}$. אה… מה? תיארתי בעבר בבלוג את בעיית $latex \mbox{P=NP}$ בתור הבעיה הפתוחה המרכזית במדעי המחשב ולא הרבה השתנה מאז – עדיין אין לנו הוכחה ש-$latex \mbox{P}\ne\mbox{NP}$ למרות שרוב מדעני המחשב חושבים שזה המצב. אז מן הסתם … להמשיך לקרוא

פרוייקט "התלמיד והמחשב", בעיות 2-3-4

התרגילים הראשונים שיש בספר של "התלמיד והמחשב" הם קלים בצורה מאכזבת, מה שגורם לעניין להיראות די רפטטיבי; לכן אני אשתדל בפתרונות שלי לא בהכרח ללכת לכיוון של הפתרון היעיל או הפשוט ביותר, אלא אנסה לנצל כל פתרון כדי להראות משהו … להמשיך לקרוא