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

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

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

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

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

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

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

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