TQBF

מתוך המכלול, האנציקלופדיה היהודית
קפיצה לניווט קפיצה לחיפוש

בתורת הסיבוכיות, השפה TQBF (קיצור ל-True quantified boolean formulas; או: QBF, QSAT) היא שפה פורמלית במחלקה PSPACE. השפה TQBF היא השפה של כל הנוסחות הבוליאניות עם כמתים שמוערכות לאמת. ניתן לראות את TQBF כהכללה ל-SAT. השפה ידועה בהיותה שפה PSPACE-Complete, כלומר לכל שפה ב-PSPACE קיימת רדוקציה פולינומית ל-TQBF.

בניגוד ל-SAT בה השאלה היא האם קיימת הצבת אמת, ב-TQBF לכל נוסחה יש ערך אמת או שקר יחיד, מכיוון שאין משתנים חופשיים.

הסבר - נוסחת SAT נראית כך:

ועבור ההצבה הנוסחה מקבלת ערך אמת בעוד עבור הנוסחה מקבלת ערך שקר.

הנוסחה השקולה ב-QBF נראית כך:

וערכה הוא אמת, מכיוון שקיימים עבורם יש הצבות אמת.

ניתן לחשוב על TQBF כעל משחק בין שני שחקנים, המשחקים בתורות. משתנים המופיעים בנוסחה עם כמת "קיים" תואמים לקיום מהלך עבור שחקן בתור כלשהו, ומשתנים המופיעים בנוסחה עם כמת "לכל" תואמים לכך שתוצאת המשחק אינה תלויה במהלך ששחקן מבצע (כלומר, כל מהלך יכול להוביל לניצחון). נוסחת TQBF שהכמת הראשון בה הוא "קיים" תואמת לנוסחת משחק בה לשחקן הראשון אסטרטגיה מנצחת (כיוון שקיים מהלך של השחקן עבורו לכל מהלך אחר של היריב, השחקן ינצח).

סקירה

בתורת הסיבוכיות, השפה QBF היא הכללה של השפה SAT בה לכל משתנה מוצמד כמת. מכיוון ש-QBF נמצאת ב-PSPACE, אין חובה לכתוב את הנוסחאות בצורת CNF מכיוון שזה ודאי לא הופך את השפה ל"קלה" יותר, אך גם לא הופך אותה לקשה יותר. מאחר שלכל משתנה מוצמד כמת, לנוסחה יש ערך אמת או שקר, והשפה QBF היא של הנוסחאות שמקבלות ערך אמת. פורמלית : דוגמה:

מתקיים .

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

ההוכחה לתוצאה המפתיעה IP = PSPACE נעשתה על ידי הצגת הוכחה אינטראקטיבית ל-QBF.

ל-QBF מספר צורות נורמליות. אחת הצורות החשובות היא הצורה הנורמלית של פרנקס אם היא מהצורה

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

וגם המחלקה מוגדרת כל השפות A עבורן קיים מוודא פולינומי ופולינום כך ש-

,

והנוסחה למעלה ניתנת לרדוקציה טריוויאלית ל-QBF.

PH ו-PSPACE

ההנחה הרווחת כיום היא ש , מכיוון שאם PH=PSPACE, אזי QBF נמצא באחת מדרגות ההיררכיה הפולינומית ולכן ההיררכיה קורסת בדרגה זאת, אף על פי שמקובל להניח שזה לא קורה[1].

פתירת QBF

ל-QBF פתרון טריוויאלי בסיבוכיות מקום ליניארית.

אלגוריתם לפתרון:

  1. אם הנוסחה ריקה, החזר אמת.
  2. עבור המשתנה הראשון x בנוסחה בצע:
    1. הצב T ב
      1. פתור את הנוסחה והצב את התוצאה ב
    2. הצב F ב
      1. פתור את הנוסחה והצב את התוצאה ב
  3. אם הכמת של x הוא "לכל":
    1. החזר
  4. אם הכמת של x הוא "קיים":
    1. החזר

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

שלמות של QBF

נרצה להראות שהשפה QBF שלמה ב-PSPACE תחת רדוקציית קארפ פולינומית, כלומר

או, בכתיב חסכני,

לשם כך נגדיר ראשית את גרף הקונפיגורציות של מכונת טיורינג M:

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

קונפיגורציה של מכונת טיורינג היא המצב הנוכחי של המכונה, דהיינו

  1. תוכן סרט העבודה
  2. מיקום המכונה על הסרט
  3. מצב המכונה

נשים לב, שמכיוון שהמכונה שלנו פולינומית במקום, קונפיגורציה בודדת שלה היא גם פולינומית במקום.

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

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

ניסיון: נגדיר את הנוסחה באופן הבא: -C'

הנוסחה הנ"ל באורך אקספוננציאלי. נגדיר פונקציה חדשה: הוא אמת אם ורק קיים מסלול בין C ל-C' באורך לכל היותר .

נשים לב שמתקיים:

משמעות הנוסחה למעלה: קיים מסלול בין ל- אם ורק אם קיימת קונפיגורציה כך שיש מסלול בין ל- ובין ל-.

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

הנוסחה הנ"ל שקולה בדיוק לנוסחה למעלה, אך היא גדלה בקצב פולינומי ולא אקספוננציאלי.

כעת, כאשר נפתח לפי הנוסחה הנ"ל, נקבל נוסחה בוליאנית עם כמתים שאורכה פולינומי באורך הקלט, וכן מתקיים

ולכן השפה QBF היא PSPACE שלמה.

ראו גם

הערות שוליים

  1. ^ Prof. Salil Vadhan, [1]

.

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

27636466TQBF