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

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

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

תכונות

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

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

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

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

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

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