משפט Valiant-Vazirani, או: איך להרוג השמות מספקות עם פונקציות תמצות אקראיות

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

אולי הבעיה הקונקרטית המפורסמת ביותר בתורת הסיבוכיות היא SAT. בבעיה הזו נתון לנו פסוק לוגי בצורת CNF, כלומר הוא נראה כך: \( C_{1}\wedge C_{2}\wedge\dots\wedge C_{k} \), כך שכל \( C_{i} \) נראה כך: \( \left(l_{1}\vee l_{2}\vee\dots\vee l_{r}\right) \), כך שכל \( l_{j} \) הוא או משתנה \( x \) או שלילה של משתנה, \( \neg x \). ל-\( l \) כזה קוראים “ליטרל”, ל-\( C \) כזה קוראים “פסוקית CNF’’, והשאלה היא זו: האם יש השמה למשתנים של הפסוק \( \varphi \) שמספקת אותו? השמה נותנת לכל משתנה ערך \( \mbox{T} \) או \( \mbox{F} \) (אמת או שקר). אם הליטרל \( l \) הוא מהצורה \( x \) הוא מקבל את הערך של \( x \) ואם הוא מהצורה \( \neg x \) הוא מקבל את הערך ההפוך לערך של \( x \); הפסוקית \( C_{i} \) מקבלת את הערך \( \mbox{T} \) אם לפחות אחד מהליטרלים שלה קיבל \( \mbox{T} \) ואחרת היא מקבלת \( \mbox{F} \); והפסוק כולו מקבל \( \mbox{T} \) רק אם כל הפסוקיות שבו קיבלו \( \mbox{T} \). תחשבו על פסוק \( \varphi \) בתור “רשימה של אילוצים”, כך שכל אילוץ הוא פסוקית, חייבים שכל האילוצים יתקיימו בו זמנית, וכל אילוץ קל יחסית לקיים - רק צריך שאחד מהליטרלים בתוכו יתקיים.

דוגמה: \( \varphi=\left(x\vee\neg y\right)\wedge\left(\neg x\vee z\right) \). זה פסוק שדי קל לספק, למשל על ידי ההשמה \( x=\mbox{\ensuremath{\mbox{T}},y=\ensuremath{\mbox{F}},z=\ensuremath{\mbox{T}}} \). יש גם השמות שלא מספקות אותו, למשל \( x=\mbox{F},y=\mbox{T},z=\mbox{F} \). אפשר, אם באמת רוצים, לספור כמה השמות מספקות יש ל-\( \varphi \)- די ברור שיש יותר מאחת.

אוקיי, תגידו, אז הבנו/נזכרנו מה הבעיה הזו. אבל למה בעיה ספציפית כזו מתחום הלוגיקה מעניינת בכלל? ובכן, בגלל שהיא האמא של הבעיות ה-NP-שלמות. יש לי פוסט שמסביר את הנושאים הללו ולכן רק תזכורת קצרה: בעיה NP-שלמה היא בעיה שאם היא נפתרת בצורה יעילה, אז עוד אלפי בעיות שכיום נחשבות קשות ולא ידוע פתרון יעיל עבורן ייפתרו גם הן. במילים אחרות, פתרון יעיל ל-SAT יהיה הסנסציה הגדולה ביותר במדעי המחשב מאז ומעולם (גם הוכחה לכך שאין פתרון יעיל ל-SAT תהיה סנסציה אדירה, אם כי צפויה קצת יותר ולכן גם מרגשת פחות). בינתיים המעמד של SAT הוא של “בעיה קשה, קשה, קשה לפתרון” (שקר גס, בפועל פותרים בעיות כאלו בעזרת היוריסטיקות ומסתדרים לא רע יחסית).

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

אז בואו נאמר שאנחנו רוצים להיות מסוגלים להבדיל רק בין שני מקרים - המקרה שבו ל-\( \varphi \) אין בכלל השמות מספקות, והמקרה שבו יש ל-\( \varphi \) השמה מספקת אחת. ויותר מזה - אנחנו מרשים לאלגוריתם שלנו להיות הסתברותי עם טעות חד-צדדית. כלומר, אם \( \varphi \) אינו ספיק, אנחנו דורשים שהאלגוריתם יעצור ובודאות יגיד “לא”, אבל אם \( \varphi \) ספיק על ידי השמה מספקת אחת בדיוק כל מה שאנחנו דורשים הוא שהוא יעצור ויגיד “כן” בהסתברות נמוכה כלשהי (כמה נמוכה? נדון בכך אחר כך). אם \( \varphi \) ספיק על ידי יותר מהשמה מספקת אחת ממש לא אכפת לנו מה האלגוריתם יעשה. האינטואיציה היא זו: אם המקרה הזה קל יותר מהבעיה הכללית, אולי הבנה של הפתרון שלו תעזור לנו להבין איך לפתור את הבעיה הכללית או היכן טמון הקושי בבעיה הכללית; ואילו אם הוא קשה מספיק לכשעצמו אז אולי נקבל אינטואיציה טובה יותר לגבי הקושי הזה. ובכן, משפט VV מראה לנו, באופן די מפתיע, שגם המקרה הזה הוא קשה למדי; ספציפית, אם יש אלגוריתם שפותר אותו נובע מכך שלכל בעיה ב-NP יש אלגוריתם הסתברותי עם טעות חד צדדית שפותר אותה, בפרט ל-SAT עצמה (בלשון סיבוכיותית, \( \mbox{RP=NP} \)). משפט VV מראה זאת על ידי תיאור של דרך לפתור את \( \mbox{SAT} \) בעזרת פתרון לבעיה הפשוטה יותר - הוא עושה זאת באמצעות רדוקציה אקראית, ואסביר עכשיו מה זה בדיוק אומר.

באופן פורמלי, המשפט אומר שאם נתון לנו פסוק CNF \( \varphi \) אז אפשר להמיר אותו (באופן הסתברותי) לפסוק \( \mbox{CNF} \) \( \varphi^{\prime} \) כך ש:

1. ההמרה מתבצעת בזמן יעיל (פולינומי באורך של \( \varphi \)).
2. אם \( \varphi \) לא ספיק אז גם \( \varphi^{\prime} \) לא ספיק.
3. אם \( \varphi \) ספיק אז בהסתברות לא רעה ל-\( \varphi^{\prime} \) יש בדיוק השמה מספקת אחת ("הסתברות לא רעה" כאן היא \( \frac{1}{8n} \) כש-\( n \) הוא מספר המשתנים של \( \varphi \)).

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

הבניה עצמה היא פשוטה באופן מפתיע. מה שנעשה יהיה להוסיף ל-\( \varphi \) עוד אילוצים; פורמלית, \( \varphi^{\prime}\left(x\right)=\varphi\left(x\right)\wedge\left(h\left(x\right)=0\right) \), כאשר \( h\left(x\right)=0 \) כאן הוא קידוד של פסוק CNF שבודק ש-\( h\left(x\right)=0 \) עבור פונקציה \( h \) שמוגרלת באופן מסויים שאסביר בקרוב. מייד נשאלת השאלה איך מקודדים את \( h\left(x\right)=0 \) בתור פסוק CNF; נדחה את השאלה הזו להמשך.

לב הרעיון, שמשתמשים בו במקומות נוספים בסיבוכיות, הוא לבחור את \( h \) מתוך אוסף של פונקציות תמצות בלתי תלויות בזוגות. עזבו אתכם ממה זה אומר באופן כללי ובואו נדבר קונקרטית. אנחנו חושבים על \( x \) (שהוא וקטור של \( \mbox{T} \) ו-\( \mbox{F} \)) בתור איבר של \( \mathbb{Z}_{2}^{n} \) - סדרה מאורך \( n \) של אפסים ואחדים - ואנחנו מגרילים מטריצה \( A\in\mathbb{Z}_{2}^{k\times n} \) עם \( k \) שורות ו-\( n \) עמודות, כך ש-\( k \) עצמו נבחר באקראי מתוך \( \left\{ 2,3,\dots,n+1\right\} \) (למה התחום המוזר הזה? יהיה הסבר, סבלנות) ובנוסף אנחנו מגרילים וקטור \( b\in\mathbb{Z}_{2}^{k} \), וכעת מגדירים \( h\left(x\right)=Ax+b \). כלומר, \( h \) תלויה בביטים של \( A \) ושל \( b \).

כדאי לחשוב על העניין כך: כל שורה \( a^{i}\in\mathbb{Z}_{2}^{n} \) של \( A \) מגדירה אילוץ מהצורה \( a^{i}\cdot x=b_{i} \) (העברתי את ה-\( b \) אגף, ומכיוון שאנחנו מעל \( \mathbb{Z}_{2} \) אין צורך לשנות סימן). עכשיו, די בבירור אם אני מגריל את \( a \) ואת \( b_{i} \) בהתפלגות אחידה אז יש ל-\( x \) נתון הסתברות של \( \frac{1}{2} \) לקיים את האילוץ, כי אם “נקפיא” את \( a \) אז עבור אחד מהערכים האפשריים של \( b_{i} \) האילוץ יתקיים ועבור הערך השני של \( b_{i} \) האילוץ לא יתקיים, ולכן הוא מתקיים בדיוק עבור חצי מהזוגות \( \left(a,b_{i}\right) \). במילים אחרות, לכל \( x \) יש הסתברות של \( \frac{1}{2} \) לשרוד כל אחד מהאילוצים, ומכיוון שכל \( k \) האילוצים נבחרים באופן בלתי תלוי זה בזה, יש ל-\( x \) סיכוי של \( 2^{-k} \) לשרוד את כל האילוצים. אם כן, \( h \) מדללת באופן אקספוננציאלי את כמות ה-\( x \)-ים שמספקים את \( \varphi \), ובגלל שיש לנו שליטה על \( k \) נוכל לבחור את רמת הדילול המדוייקת שאנחנו צריכים, בהסתברות לא רעה. פורמלית: \( \mbox{Pr}_{h}\left[h\left(x\right)=0\right]=2^{-k} \). אסמן \( p=2^{-k} \) לצורך פשטות.

בינתיים כל מה שעשיתי נראה מטופש להפליא. למה בכלל הגרלתי \( A \)? הרי היא לא סייעה לי בטיעון. הייתי יכול להגריל רק את \( b \) ולהשוות אותו בכל פעם ל-\( x_{1}+x_{2}+\dots+x_{n} \) וחסל. אלא שאני זקוק לעוד תכונה של ה-\( h \) שאני מגריל - בדיוק תכונת הבלתי תלויות בזוגות שהוזכרה קודם; בלעדיה אני באמת לא אוכל לעשות הרבה. מה שאני רוצה לומר הוא שלא רק ש-\( h \) מדללת “הרבה”, אלא גם שהיא מדללת באופן שיוצר פער בין, נאמר, דילול שמשאיר רק השמה מספקת אחת בחיים ודילול שמשאיר שתיים כאלו בחיים. בשביל להראות את זה אני צריך להראות שההסתברות לכך ששתי השמות נתונות שונות זו מזו יישארו בחיים קטן משמעותית מההסתברות של השמה אחת להישאר בחיים. ספציפית, אני רוצה לחשב את \( \mbox{Pr}\left[h\left(x\right)=0\wedge h\left(y\right)=0\right] \) עבור \( x\ne y \). כאן מגיע תעלול רעיוני שהוא לב ההוכחה ולטעמי הוא רעיון מקסים ביותר, למרות שהוא גם מאוד פשוט.

הרעיון הוא כזה: מכיוון ש-\( x\ne y \) יש ביט, נאמר \( i \), כך ש-\( x_{i}=0 \) ו-\( y_{i}=1 \) (או הפוך). נסתכל על אילוץ \( \left(a^{k},b_{k}\right) \) כלשהו ש-\( x \) מספק, כלומר \( a^{k}\cdot x=b_{k} \). אז מכיוון ש-\( x_{i}=0 \), זה אומר שהביט במקום ה-\( i \) בוקטור \( a^{k} \) לא משנה את הערך של \( a^{k}\cdot x \); בפרט, אם אגדיר \( c^{k} \) כך ש-\( a^{k}=c^{k} \) בכל ביט פרט לביט ה-\( i \) ושם הם הפוכים, אז יתקיים גם \( c^{k}\cdot x=b_{k} \).

לעומת זאת, לא ייתכן ש-\( a^{k}\cdot y=c^{k}\cdot y \), כי הערכים של \( a^{k}\cdot y,c^{k}\cdot y \) נבדלים ב-1 בדיוק (הסבירו את זה לעצמכם!) ולכן \( y \) מקיים בדיוק אחד משני האילוצים \( a^{k}\cdot y=b_{k} \) ו-\( c^{k}\cdot y=b_{k} \), כלומר \( y \) מקיים בדיוק חצי מהאילוצים ש-\( x \) מקיים, כלומר ההסתברות לכך ש-\( y \) יקיים אילוץ בהינתן ש-\( x \) מקיים אותו היא \( \frac{1}{2} \), כלומר ההסתברות ש-\( x,y \) יקיימו אילוץ מסויים בו זמנית היא \( \frac{1}{4} \), ולכן ההסתברות ששניהם יקיימו זמנית את כל האילוצים היא \( 4^{-k} \), כלומר \( \mbox{Pr}\left[h\left(x\right)=0\wedge h\left(y\right)=0\right]=p^{2} \). אם הבנתם את זה - הבנתם את העיקר בהוכחה (שימו לב שהעיקר הזה הוא תכונה כללית של פונקציות תמצות בלתי תלויות בזוגות; זה לא משהו שייחודי למשפט הנוכחי).

עכשיו בואו נבין איך זה עוזר לנו. נסמן ב-\( S \) את קבוצת ההשמות שמספקות את \( \varphi \). בבירור אם \( S \) ריקה אז אין השמה שמספקת את \( \varphi^{\prime} \) (כי כל השמה שמספקת את \( \varphi^{\prime} \) בפרט צריכה לספק את \( \varphi \)). לכן נניח ש-\( \left|S\right|\ge1 \). נסמן ב-\( N \) את מספר ההשמות ב-\( S \) שמקיימות \( h\left(x\right)=0 \); זה משתנה מקרי שתלוי בבחירת \( h \). אנחנו רוצים למצוא מהו \( \mbox{Pr}_{h}\left[N=1\right] \). דרך אחת לעשות זאת היא כך: \( \mbox{Pr}_{h}\left[N=1\right]=\mbox{Pr}_{h}\left[N\ge1\right]-\mbox{Pr}_{h}\left[N\ge2\right] \) (הסבירו לעצמכם למה!) ולכן, אם אנחנו רוצים למצוא חסם מלמטה עבור \( \mbox{Pr}_{h}\left[N=1\right] \) (אין צורך לחשב את ההסתברות במדויק) מספיק למצוא חסם מלמטה עבור \( \mbox{Pr}_{h}\left[N\ge1\right] \) וחסם מלמעלה עבור \( \mbox{Pr}_{h}\left[N\ge2\right] \).

כדי להקל על הסימונים, בואו נסמן בתור \( A_{x} \) את המאורע “\( h\left(x\right)=0 \)” (כלומר, \( A_{x} \) היא קבוצת ה-\( h \)-ים שמקיימים \( h\left(x\right)=0 \)) ובדומה נסמן ב-\( A_{x,y} \) את המאורע “\( h\left(x\right)=0\wedge h\left(y\right)=0 \)”. כעת:

\( \mbox{Pr}_{h}\left[N\ge2\right]=\mbox{Pr}\left[\bigcup_{x<y\in S}A_{x,y}\right]\le\sum_{x<y\in S}\mbox{Pr}\left[A_{x,y}\right]=\sum_{x<y\in S}p^{2}={\left|S\right| \choose 2}p^{2} \)

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

לחסום את \( \mbox{Pr}\left[N\ge1\right] \) מלמטה זה קצת יותר מחוכם. התעלול הוא להשתמש בעקרון הההכלה וההפרדה. כשמפעילים אותו על המקרה הנוכחי, מקבלים:

\( \mbox{Pr}\left[N\ge1\right]=\mbox{Pr}\left[\bigcup A_{x}\right]-\mbox{Pr}\left[\bigcup A_{x,y}\right]+\mbox{Pr}\left[\bigcup A_{x,y,z}\right]-\dots \)

(למה? ובכן, אם נכפול את שני אגפי המשוואה במספר ה-\( h \)-ים הכולל האפשרי, נוכל להפסיק לדבר על הסתברות ולעבור לדבר על קומבינטוריקה סופית טהורה ואז יהיה יותר ברור שעקרון ההכלה וההפרדה תקף כאן). הנקודה הקריטית כאן היא שה”זנב” \( \mbox{Pr}\left[\bigcup A_{x,y,z}\right]-\mbox{Pr}\left[\bigcup A_{x,y,z,w}\right]+\dots \) הוא חיובי, כי אפשר לפרק אותו לזוגות של “משהו חיובי פחות משהו קטן ממנו”. לכן אפשר להיפטר מהזנב לגמרי:

\( \mbox{Pr}\left[N\ge1\right]\ge\mbox{Pr}\left[\bigcup A_{x}\right]-\mbox{Pr}\left[\bigcup A_{x,y}\right]=\left|S\right|p-{\left|S\right| \choose 2}p^{2} \)

ועכשיו מחיבור שני האי שוויונות שמצאנו, נקבל:

\( \mbox{Pr}\left[N=1\right]=\mbox{Pr}_{h}\left[N\ge1\right]-\mbox{Pr}_{h}\left[N\ge2\right]\ge\left|S\right|p-2{\left|S\right| \choose 2}p^{2}\ge\left|S\right|p-\left(\left|S\right|p\right)^{2} \)

עכשיו, את הפונקציה \( f\left(t\right)=t-t^{2} \) קל לחקור אם יודעים טיפה אינפי; מהר מאוד רואים שבקטע \( \left[\frac{1}{4},\frac{1}{2}\right] \) היא פונקציה עולה, לכן המינימום שלה מתקבל ב-\( t=\frac{1}{4} \) והוא \( \frac{1}{4}-\frac{1}{16}=\frac{3}{16}>\frac{1}{8} \). לכן הגענו למסקנה הבאה: אם \( \frac{1}{4}\le\left|S\right|p\le\frac{1}{2} \), אז \( \mbox{Pr}\left[N=1\right]\ge\frac{1}{8} \). לא רע בכלל!

עכשיו, מהו \( p \)? כזכור, \( p=2^{-k} \). ומי זה \( k \)? את \( k \) בחרנו באקראי בתחום \( \left\{ 2,\dots,n+1\right\} \). אז כדי שיתקיים \( \frac{1}{4}\le\left|S\right|p\le\frac{1}{2} \) צריך שיתקיים \( 2^{k-2}\le\left|S\right|\le2^{k-1} \). אבל, מכיוון ש-\( 1\le\left|S\right|\le2^{n} \), זה בהכרח קורה לאחד מה-\( k \)-ים בדיוק בתחום \( \left\{ 2,\dots,n+1\right\} \), שאני מקווה שעכשיו נראה קצת יותר ברור. לכן ההסתברות שלנו לבחור \( k \) “נכון” היא \( \frac{1}{n} \) (גודל התחום), ולכן ההסתברות של הרדוקציה כולה לעבור היא לפחות \( \frac{1}{8n} \) - בדיוק מה שהבטחתי שאוכיח. סיימנו!

ובכן, לא, עוד לא סיימנו כי עוד לא הסברתי איך לקודד את \( h\left(x\right)=0 \). זה לא מובן מאליו; צריך להיזהר ולא לקודד את הביטוי הזה על ידי נוסחת CNF גדולה מדי. כדי לעשות את זה אהיה חייב להשתמש במשתני עזר; קיימת הוכחה לכך שאפילו מקרה פרטי - הנוסחה \( x_{1}\oplus\dots\oplus x_{n}=0 \), הידועה גם בתור הפונקציה PARITY - לא ניתן לקודד כפסוק CNF קצר (פולינומי) באופן כזה שכל השמה למשתנים תחזיר את הערך הנכון של הפרדיקט \( x_{1}\oplus\dots\oplus x_{n}=0 \). אז מה שאעשה יהיה שונה: אני אקודד את \( h\left(x\right)=0 \) על ידי פסוק \( \psi\left(x,z\right) \) כך ש-\( z \) הם משתני עזר, כך שאם \( h\left(x\right)=0 \) אז קיימת השמה יחידה למשתני העזר כך ש-\( \psi\left(x,z\right)=\mbox{T} \); ואחרת אף השמה לא תספק את \( \psi \). לבקיאים רק אציין שאפשר לעצור כבר כאן באמירה “ניקח מכונת טיורינג דטרמיניסטית שבודקת אם \( h\left(x\right)=0 \) ומקבלת אם כן, ו-\( \psi \) יהיה קידוד קוק-לוין של הריצה שלה” אבל לטובת אלו מכם שאין להם מושג מה אמרתי, או לא זוכרים את הפרטים של קוק-לוין, אתן כאן בניה ישירה. ולמען הסר ספק: אני עצמי לא ממש זוכר את הפרטים של קוק-לוין ומעדיף הרבה יותר לראות בניה ישירה מאשר את נפנוף הידיים המתועב הזה.

בואו נתחיל ממשהו פשוט: איך אני מקודד ב-CNF את \( x\oplus y \)? פשוט מאוד: \( \left(x\vee y\right)\wedge\left(\neg x\vee\neg y\right) \). מה קורה פה? אם \( x=y \) אז או ש-\( x\vee y \) לא יסתפק (אם \( x=y=\mbox{F} \)) או ש-\( \neg x\vee\neg y \) לא יסתפק (אם \( x=y=\mbox{T} \)). ההכללה של זה לשלושה משתנים לא מסובכת: את \( x\oplus y\oplus w \) נקודד בתור \( \left(x\vee\neg y\vee\neg w\right)\wedge\left(\neg x\vee\neg y\vee w\right)\wedge\left(\neg x\vee y\vee\neg w\right)\wedge\left(x\vee y\vee w\right) \). האם אתם רואים את העקרון? בכל זוג סוגריים צריכים להיות מספר זוגי של שלילות. כך, אם יש לנו השמה כלשהי למשתנים שבה מספר זוגי של משתנים קיבל \( \mbox{T} \), יהיה זוג סוגריים שיחזיר \( \mbox{F} \) (בדיוק זה שבו אותם המשתנים מופיעים עם \( \neg \)) ולעומת זאת כל השמה שבה מספר אי זוגי של משתנים קיבל \( \mbox{T} \) בהכרח תספק את כל זוגות הסוגריים (כי אז אז או שאחד מהמשתנים שקיבלו \( \mbox{T} \) מופיע בלי \( \neg \), או שאחד מהמשתנים שקיבל \( \mbox{F} \) מופיע עם \( \neg \)). אלא שאם יש לנו \( n \) משתנים, זה אומר שנצטרך ליצור פסוק עם המון פסוקיות - \( 2^{n-1} \) (פורמלית, \( {n \choose 0}+{n \choose 2}+\dots \) ויש תעלולים שמראים שהסכום אכן יוצא \( 2^{n-1} \)). בקיצור, אקספוננציאלי. אז השיטה הישירה לא תעבוד כאן ואנחנו חייבים משהו מתוחכם יותר.

הנה תעלול אפשרי אחד: אם אנחנו רוצים לקודד את \( x_{1}\oplus x_{2}\oplus\dots\oplus x_{n} \), אפשר תחת זאת לקודד את \( \left(z_{1}=x_{1}\oplus x_{2}\right)\wedge\left(z_{2}=z_{1}\oplus x_{3}\right)\wedge\dots\wedge\left(z_{n-1}=z_{n-2}\oplus x_{n}\right)\wedge\left(z_{n-1}\right) \). זה יפתור לנו את הבעיה, בהינתן שאפשר לקודד משהו כמו \( z=x\oplus y \) בעזרת פסוק CNF מאורך פולינומי. ובכן, איך מוצאים דבר כזה באופן שיטתי, בלי ניסוי וטעיה? ראשית כותבים את \( z\ne x\oplus y \) בתור DNF דווקא; לכתוב DNF זה קל כי פשוט מבצעים \( \vee \) על כל ארבע ההשמות האפשריות שיספקו את \( z\ne x\oplus y \): \( \left(x\wedge y\wedge z\right)\vee\left(\neg x\wedge\neg y\wedge z\right)\vee\left(\neg x\wedge y\wedge\neg z\right)\vee\left(x\wedge\neg y\wedge\neg z\right) \). עכשיו מפעילים שלילה על הפסוק כולו ומשתמשים בכללי דה-מורגן, ומקבלים \( \left(\neg x\vee\neg y\vee\neg z\right)\wedge\left(x\vee y\vee\neg z\right)\wedge\left(x\vee\neg y\vee z\right)\wedge\left(\neg x\vee y\vee z\right) \). זה מסיים את ההוכחה כולה.

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