פונקציית דן

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

תהי G חבורה הנוצרת על ידי קבוצה X עם קבוצת יחסים R. כל מילה w המייצגת את איבר היחידה אפשר להציג כמכפלה של צמודים הפענוח נכשל (שגיאת המרה. השרת ("https://wikimedia.org/api/rest_") השיב: "Cannot get mml. Server problem."): {\displaystyle \ w=(p_{1}r_{1}p_{1}^{-1})\cdots (p_{t}r_{t}p_{t}^{-1})} , כאשר $\ r_{1},\dots ,r_{t}\in R^{\pm 1}$ הם יחסים. המספר המינימלי של יחסים כאלה הוא השטח של w. פונקציית דן המתאימה ל-X מוגדרת כך ש-$\ f(n)$ הוא השטח הגדול ביותר של מילים באורך n.

מגדירים יחס שקילות על פונקציות, כך ש-הפענוח נכשל (שגיאת המרה. השרת ("https://wikimedia.org/api/rest_") השיב: "Cannot get mml. Server problem."): {\displaystyle \ f\equiv g} אם קיים קבוע c כך ש-הפענוח נכשל (שגיאת המרה. השרת ("https://wikimedia.org/api/rest_") השיב: "Cannot get mml. Server problem."): {\displaystyle \ f(n)\leq c\cdot g(cn)+cn} , וכן להפך. כל שתי פונקציות דן של אותה חבורה שקולות זו לזו. בפרט, אם פונקציית דן שקולה לחזקה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ n^{\alpha}} , אז המעלה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ \alpha} מוגדרת היטב. יש חבורות מוצגות סופית עם פונקציות דן כאלה עבור קבוצה צפופה של ערכים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2\leq \alpha} . פונקציית דן עשויה להיות אקספוננציאלית, אפילו עבור חבורה מטא-אבלית.

כל פונקציית דן תת-ריבועית היא ליניארית. חבורה היא היפרבולית אם ורק אם יש לה פונקציית דן ליניארית. יש חבורות רבות עם פונקציית דן ריבועית: כל חבורה אבלית, כל חבורה חופשית-על-ציקלית, חבורת תומפסון, וגם החבורות הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ \operatorname{SL}_n(\mathbb{Z})} כאשר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle n \geq 5} .

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

פונקציית דן של תת-חבורה עשויה לגדול מהר יותר מזו של החבורה עצמה.

ראו גם

• גידול של חבורה
• בעיות דן

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

שגיאות פרמטריות בתבנית:מיון ויקיפדיה
שימוש בפרמטרים מיושנים [ דרגה ] פונקציית דן31593883