פונקציית זוגיות

באלגברה בוליאנית, פונקציית זוגיות היא פונקציה בוליאנית המחזירה 1 אם מספר האחדות בווקטור הקלט הוא אי זוגי.

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

תכונות

פונקציית הזוגיות היא פונקציה בוליאנית סימטרית.

פונקציית הזוגיות ב-n משתנים ושלילתה הן היחידות עבורן הצורה הנורמלית הדיסיונקטיבית תהיה בהכרח בעלת המספר המקסימלי של $2^{n-1}$ פרדיקטים באורך n וכן הצורה הנורמלית הקוניוקטיבית תהיה בעלת המספר המקסימלי של $2^{n-1}$ פסוקיות מאורך n.^[1]

סיבוכיות מעגלים

בשנות השמונים המוקדמות של המאה העשרים מריק פורסט, ג'יימס סאקס ומייקל סיפסר^[2] ובאופן בלתי תלוי מיקלוס אג'טאי^[3] מצאו חסם תחתון על-פולינומי על הגודל של מעגלים בוליאניים קבועי-עומק עבור פונקציית הזוגיות. כלומר, הם הראו כי לא קיים מעגל קבוע-עומק מגודל פולינומי שיכול לחשב את פונקציית הזוגיות. תוצאות דומות הושגו גם עבור פונקציות הרוב, הכפל והסגור הטרנזיטיבי, על ידי רדוקציה למקרה של פונקציית הזוגיות.^[2] עד אותו זמן היו ידועים רק חסמים תחתונים ליניאריים עבור פונקציות טבעיות אחדות.^[2] בעקבות זאת פורסמו מספר הולך וגדל של חסמים תחתונים. לבסוף, בשנת 1984 ג'ואן הסטאד (שזכה ב-1994 בפרס גדל עבור עבודתו זו) מצא חסם תחתון אקספוננציאלי הדוק על גודל המעגלים הבוליאניים קבועי העומק עבור פונקציית הזוגיות. למעשה, למת המיתוג של הסטאד טומנת בחובה את הקושי הטכני שבמציאת חסמים תחתונים שכאלו.^[1]

הגרסה האינסופית

פונקציית זוגיות אינסופית היא פונקציה $f\colon \{0,1\}^{\omega }\to \{0,1\}$ הממפה כל מחרוזת בינארית אינסופית ל-0 או 1, והיא בעלת התכונה הבאה: אם $\ w$ ו- $\ v$ הן מחרוזות בינאריות אינסופיות השונות זו מזו רק במספר סופי של קואורדינטות, אז $\ f(w)=f(v)$ אם ורק אם $\ w$ ו- $\ v$ שונות זו מזו במספר סופי של קואורדינטות. בהנחת אקסיומת הבחירה ניתן להוכיח בקלות שפונקציית זוגיות אינסופית קיימת וישנן $2^{\mathfrak {c}}$ פונקציות כאלו - כמספר כל הפונקציות מ- $\ \{0,1\}^{\omega }$ ל- $\ \{0,1\}$ . מספיק לקחת נציג אחד לכל מחלקת שקילות של היחס $\approx$ המוגדר כך: $w\approx v$ אם ורק אם $\ w$ ו- $\ v$ שונים במספר סופי של קואורדינטות. בהינתן נציגים כאלו, נוכל למפות את כולם ל-0. יתר ערכי $\ f$ ייקבעו באופן חד משמעי. לעיתים קרובות משתמשים בפונקציות זוגיות אינסופיות בתאוריה של מדעי המחשב ובתורת הקבוצות בשל הגדרתם הפשוטה - ומצד שני - הסיבוכיות התיאורית שלהן. למשל, ניתן להראות שתמונה הפוכה $\ f^{-1}[0]$ היא קבוצת לא-בורל.

הערות שוליים

^ ¹ ² Ingo Wegener, Randall J. Pruim, Complexity Theory, 2005, ISBN 3540210458, p. 260
^ ¹ ² ³ Merrick Furst, James Saxe and Michael Sipser, "Parity, Circuits, and the Polynomial-Time Hierarchy", Annu. Intl. Symp. Found.Coimputer Sci., 1981, Theory of Computing Systems, vol. 17, no. 1, 1984, pp. 13–27, doi:10.1007/BF01744431
^ Miklós Ajtai, " $\Sigma _{1}^{1}$ -Formulae on Finite Structures", Annals of Pure and Applied Logic, 24 (1983) 1–48.

[wp-1] ¹ ² Ingo Wegener, Randall J. Pruim, Complexity Theory, 2005, ISBN 3540210458, p. 260

[FSS-2] ¹ ² ³ Merrick Furst, James Saxe and Michael Sipser, "Parity, Circuits, and the Polynomial-Time Hierarchy", Annu. Intl. Symp. Found.Coimputer Sci., 1981, Theory of Computing Systems, vol. 17, no. 1, 1984, pp. 13–27, doi:10.1007/BF01744431

[3] Miklós Ajtai, " $\Sigma _{1}^{1}$ -Formulae on Finite Structures", Annals of Pure and Applied Logic, 24 (1983) 1–48.

[1]

[2]

[3]