חזרה

סילבוס

מספר קורס 0368-4155-01
שם הקורס האם Bpp שווה ל-P
יחידה אקדמית הפקולטה למדעים מדויקים ע"ש ריימונד ובברלי סאקלר -
מדעי המחשב
מרצה פרופ' אמנון תא שמעצרו קשר
צור קשר דוא"ל: amnon@tauex.tau.ac.il
שעות קבלה בתאום מראשבניין: צ'ק פוינט , חדר: 245
אופן ההוראה שיעור
שעות סמסטריאליות 3
סמסטר ב' תשפ"א
יום ד
שעות 14:00-17:00
בניין
חדר
אין סילבוס

תוכן הקורס ומטרתו

בעיה מרכזית בתיאוריה של מדעי המחשב היא האם BPP=P, כלומר, האם כל בעיה שנתנת לפתרון על ידי אלגוריתם הסתברותי יעיל, יש אלגוריתם דטרמנ?סטי יעיל הפותר אותה. כיום ידוע שהבעיה קשורה (וכמעט שקולה) לבעיה של הוכחת חסמים תחתונים על מעגלים בוליאניים לא אוניפורמים. מטרת הקורס היא להסביר קשר זה.

אנו נתחיל עם hardness vs. randomness paradigm ונראה כי קושי גורר דרנדומיזציה. אנו נדבר גם על רדוקציות לקושי בממוצע. לאחר מכן נדבר על משפטי Karp-Lipton ועל התוצאה של IKW עבור NEXP. נסיים חלק זה על ידי שנראה חסמים תחתונים למעגלים (אריתמטים או בוליאנים) תחת ההנחה של PIT יש אלגוריתמים דטרמנסטים יעילים.

בזמן שנותר אנו נדון ב easy witness method ועידונים של השיטה לחסמים על משפחות מעגלים פשוטות יותר.



לסילבוס המפורט
מטלות הקורס

עבודת בית

ייתכנו מטלות נוספות
רשימת המטלות המלאה, תופיע בסילבוס המפורט של הקורס.

קורסי קדם נדרשיםסיבוכיות (03683168)


tau logohourglass00:00