ברור שהבנייה לא נתקעת על i מסוים, מכיוון שבמקרה כזה הייתה רדוקציה טריוויאלית מ-SAT ל-L, אבל המכונות formula_38 הן פולינומיות, וזה סותר את ההנחה formula_36.
לכן מילאנו את התנאי שהשפה L אינה פולינומית. כעת נניח שיש פונקציה formula_69 עושה רדוקציה פולינומית מ-SAT ל-L. נרצה להראות שזה גורר ש-SAT פתירה בזמן פולינומי (וכנגד ההנחה שלנו, כמובן)
הוכחה. מאחר ש formula_70 רצה לכל היותר בזמן formula_71, מתקיים formula_72. חייב להיות formula_73 כך שלכל formula_74 מתקיים formula_75. מכיוון ש-formula_73 קבוע, אפשר פשוט לפתור את כל הבעיות מאורך קטן או שווה לו בזמן אקספוננציאלי.
עכשיו נניח שיש לנו נוסחה formula_77 כך שformula_78. אם formula_79 לא בטווח של formula_80, אז formula_81. אחרת, formula_82 כש-formula_83 וformula_84 אם ורק אם formula_85. עד כה השגנו שformula_86. אז formula_87 אם formula_88. מאחר שformula_89 מתקיים &lt;chem&gt;k&gt;j &lt;/chem&gt; אז formula_90. אם formula_91 אז אפשר לבדוק אם formula_92 ב-SAT ולכן גם אפשר לבדוק אם formula_93 ב-SAT. אחרת נריץ את האלגוריתם רקורסיבית (לא יותר מ-n פעמים) מכיוון שגודל הפלט גדל בין הרצה להרצה, וכל ריצה מתבצעת בזמן פולינומי.
לוקרישה מוט
לוקרישיה מוט (; 3 בינואר 1793, ננטקט, מסצ'וסטס, ארצות הברית – 11 בנובמבר 1880, צ'לטנהאם, פנסילבניה, ארצות הברית) הייתה קווייקרית אמריקאית, פעילה למען זכויות הנשים וביטול העבדות ורפורמטורית חברתית. מוט הרצתה בפני קהלים שונים על ביטול העבדות והייתה אחת הנשים שלקחו חלק בניסוח הצהרת ההמלצות שהובאה לדיון ואישור במהלך ועידת סנקה פולס ב-1848.
היכולות הרטוריות של לוקרישיה מוט הפכו אותה לדוברת מרכזית של התנועה לביטול העבדות, תנועת הנשים ותנועת הרפורמה. לאחר ביטול העבדות, היא פעלה למען זכות ההצבעה לשחורים.
ילדות וחינוך.
לוקרשיה קופין נולדה בננטקט מסצ'וסטס, ב-3 בינואר 1793 למשפחת בנקאים מבוססת. הילדה השנייה מתוך שמונת הילדים של אנה פולג'ר ותומאס הארון. בגיל 13 היא נשלחה ללמוד במכינה ב- Dutchess County במדינת ניו יורק אשר נוהלה על ידי קווייקרים. לאחר לימודיה היא השתלבה במכינה כמורה. בעת עבודתה כמורה, גילתה שהקולגות הגברים קיבלו שכר גבוה באופן משמעותי משכרן של המורות. אירוע זה היה מהראשונים שגיבשו את מודעותה בנוגע לזכויות נשים. ב־1811 היא נישאה לג'יימס מוט שהיה מורה גם הוא. המשפחה של לוקרשיה קופין עברה לפילדלפיה והיא בעלה ומורים וקיווקרים נוספים הצטרפו אליהם. בשנת 1815 נפטר אביה של לוקרשיה והותיר את אמה עם חובות כבדים. גם משפחת מוט סבלה ממצוקה כלכלית. אנה קופין, חזרה לעבוד שוב כזבנית, לוקרישיה לימדה וג'יימס מוט התחיל לעבוד כשותף בעסקי האריגה עם דודו ובהמשך הוא סחר בכותנה. אך, בגלל התנגדותו להעסקת עבדים הוא עבר לסחור בצמר.
אמונה דתית.
הבסיס לכל פעילותה של מוט למען זכויות נשים וביטול העבדות הייתה אמונתה הנוצרית הקוויקרית. כבר בגיל 27, היא הוסמכה כמטיפה ובשנות העשרים של המאה ה-19 מוט נסעה לקהילות שונות והרצתה על דת ורפורמות חברתיות. התאולוגיה של מוט הושפעה מהאונטריאניזם (אמונה באל אחד ולא בשילוש הקדוש) והיא הייתה חלק מקבוצה של ליברלים דתיים שהקימו את Free Religious Association ב-1867. מוט האמינה שגברים ונשים שווים בפני האל ולכולם, ללא קשר למין, גזע או אמונה דתית, יש אור פנימי. האור הפנימי הוא בעת ובעונה התגלות של הטבע הפנימי הרוחני האמיתי של כל אדם ונוכחות של האלהות בנפשו של האדם.
מוט ביחד עם קבוצת מנהיגים קווייקרים אחרים הקימו את מכללת סוורת'מור שדגלה בחינוך שוויוני ללא הפרדה גזעית על בסיס התפיסה הקוויקרית.
התנועה לביטול העבדות.
מאמצים מוקדמים לביטול העבודות.
כמו קווייקרים רבים, מוט החשיבה את העבדות כרוע. היא קווייקרים נוספים סירבו להשתמש בסחורות שנוצרו על בסיס ניצול עבדים. בשנת 1821, מוט הוכרה כדרשנית קווייקרית (Quaker minister) על בסיס כישורי הנאום שלה והייתה האישה היחידה שדיברה באסיפות בפילדלפיה. בתמיכת בעלה, היא נסעה לעיתים קרובות ודרשה בקהילות השונות על עיקרי האמונה הקוויקירית. בדרשות היא תייחסה גם לחרם על מוצרים שיוצרו על ידי עבדים וחיזקה את ההתנגדות הדתית לעבדות. בשנת 1833, היא הקימה בעזרת ג'יימס מוט את האגודה אמריקאית לביטול העבדות. היא שילבה את המאבקים בהם האמינה והקימה את Philadelphia Female Anti-Slavery Society בשיתוף עם עוד נשים שחורות ולבנות. מהקמתו הארגון פעל נגד עבדות, גזענות ושוביזם. מוט פיתחה קשרים הדוקים עם הקהילה השחורה בפילדלפיה והטיפה גם בכנסיות של קהילות אפרו-אמריקאיות. למרות הרדיפות על ידי התומכים בעבדות ובעיות בריאותיות, מוט המשיכה בפעילותה לסיום העבודות, סייע לעבדים נמלטים ועסקה בפעילות צדקה. מוט ופעילות נוספות ארגנו ירידים להעלאת המודעות וגיוסו תרומות לתנועה.
המעורבות של נשים בתנועה לביטול העבדות לא הייתה מקובלת חברתית. גברים פעילים בתנועה התנגדו להופעות של נשים במרחב הציבורי ובייחוד לנשיאת נאומים. באספה הכללית של Congregational church (זרם בכנסייה הפרוטסטנטית), הוחלט כי ייצא מכתב מהכמרים המזהיר נשים כי הרצאה מול קהל מנוגדת להוראה של פאולוס שנשים נדרשות לשמור על שקט בכנסייה.(1 טימותי 2:12) קבוצה אחרת של גברים התנגדה לכך שנשים ירצו מול קהל מעורב וכינו זאת "הפקרות". ההתנגדות נבעה, בין היתר, מפופולריות הגואה שרה ואנג'לינה גרימקה ונשים נוספות שהיו רטוריקניות מעולות שגייסו תמיכה בתנועה לביטול העבדות.
מוט השתתפה בכל שלוש הוועידות לביטול העבדות של נשים אמריקאיות (1837, 1838, 1839). במהלך הוועידה שהתקיימה ב-1838 בפילדלפיה, אספסוף הרס את מקום המפגש הקבוע של התנועה. מוט ונשים שחורות ולבנות יצאו ביחד מהבניין שהן מגינות האחת על השנייה. ההמון המשיך לביתה של מוט ולשכונות של שחורים בפילדלפיה. מוט חיכתה מתוך הבית, מוכנה להתמעט עם יריביה האלימים.
הכנס הבינלאומי לביטול העבדות.
ביוני 1840, מוט השתתפה בכנס הבינלאומי לביטול העבדות בלונדון, אנגליה. אף על פי שמוט הייתה אחת מתוך ששת הנציגים במשלחת, לפני שהוועידה החלה, הנציגים הגברים ערכו הצבעה בנושא השתתפות נשים בכנס. הנשים נדרשו לשבת באזור מופרד באולם. מנהיגים גברים של התנועה לביטול העבדות התנגדו שמאבק לזכויות נשים יהיה מקושר למאבק לסיום העבדות ברחבי העולם. הם חששו מהסטת הדיון למאבק על זכויות נשים ובחרו לקבל את הנורמות החברתיות של התקופה. מספר גברים אמריקאים (וונדל פיליפס, נתנאל פיבודי רוג'רס, פרופ' ויליאם אדם וצ'ארלס לנוקס רמונד (Charles Lenox Remond)) שהשתתפו בכנס, מחו על הדרת הנשים וישבו איתם באזור הוקצה לנשים לאות מחאה. אליזבת קיידי סטנטון ובעלה הנרי סטנטון השתתפו בכנס בזמן בירח הדבש שלהם ומאז סטנטון ומוט הפכו לחברות ובעלות ברית.
הצייר בנימין רוברט היידון צייר את באי הוועידה. בציור מונצחות מוט ופעילות בריטיות, למשל מרי אן ראוסון (Mary Anne Rawson), אליזבת פיז ניצ'ול (Elizabeth Pease Nichol) ואחרות.
מוט חזרה עם אנרגיות מחודשות מאנגליה לאחר שפגשה פעילות מאנגליה וסקוטלנד לביטול העבדות שעודדו אותה להמשיך בפועלה. היא משיכה להרצות בעיקר בצפון ניו יורק ובוסטון. מוט נסעה גם למדינות בארצות הברית שתמכו בעבדות ונאמה ברחבי בולטימור, מרילנד ובערים במדינת וירג'יניה. היא נפגשה עם בעלי עבדים על מנת לדון איתם במוסריות של עבדות. במחוז קולומביה, מוט תזמנה את הרצאתה עם חזרת הקונגרס מפגרת חג המולד; יותר מ-40 חברי קונגרס נכחו בהרצאתה. כמו כן, למוט הייתה פגישה רשמית עם הנשיא ג'ון טיילר שהתרשם מהרהיטות שלה, אמר, "היית רוצה שמר קלהון גם יפגוש אותך, בהתייחסו לסנטור שהיה הנציג הבולט של מדינות הדרום והתנגד לביטול העבדות.
ב־1850, לאחר שנחקק חוק העבד הנמלט, משפחת מוט פתחה את ביתה לעבדים נמלטים והם היו חלק ממסילת הרכבת המחתרתית. הסיוע לעבדים נמלטים הגביר את המחויבות של מוט לפציפיזם.
מפלגת החירות.
שמה של לוקרשיה מוט הלך לפנייה כנואמת, פעילה למען זכויות עבדים ונשים. בכינוס השני של מפלגת החרות שהייתה מורכבת מפעילים של התנועה לביטול העבדות, הועלה שמה כמועמדת לתפקיד סגנית נשיא ארצות הברית. בהצבעה שנערכה בזמן הוועידה, מוט קיבלה 5 קולות מתוך 84 והייתה המועמדת התשיעית של המפלגה.
זכויות נשים.
ועידת סנקה פולס.
שמונה שנים לאחר פגישתן הראשונה, אליזבת קיידי סטנטון ומוט נפגשו בזמן שהאחרונה הגיע לבקר את אחותה, מרתה קופין רייט, בווטרלו, ניו יורק. סטנטון גרה באותו הזמן בסנקה פולס. במהלך פגישה חברתית החליטו מוט, מרי אן מקלינטוק, מרתה קופין רייט, אליזבת קיידי סטנטון וג'יין האנט שהגיע הזמן לדון בפומבי בזכויות החברתיות, האזרחיות והדתיות של נשים. סטנטון לקח את המשימה לכתוב את המסמך בו ידונו במהלך הוועידה. היא ביססה את הצהרת ההמלצות על הכרזת העצמאות של ארצות הברית. המסמך כלל 18 הצהרות ו- 11 החלטות הדורשות הכרה של נשים כחברות שוות בחברה. סטנטון הוסיפה סעיף בו את דרישה לזכות הצבעה לנשים. אפילו מוט, חשבה שסעיף זה רדיקלי.
במהלך שני ימי הוועידה, 19-20 ביולי 1848, לוקרישה וג'יימס מוט לקחו חלק פעיל בדיונים. מוט פתחה את היום שני בנאום וג'יימס מוט היה יושב ראש מושב הבוקר של היום השני משום שעדיין לא היה מקובל שנשים ישמשו כיושבת ראש בכינוסים בהם השתתפו גברים ונשים. מתוך 300 המשתתפים, 100 חתמו על הצהרת ההמלצות ומוט, הייתה אחת מהן.
"Discourse on Woman".