חשיבותו של משפט קוק-לוין אינה רק בתכונה של SAT שעולה ממנו, אלא גם בכך שהוא מאפשר להוכיח בקלות עבור בעיות רבות נוספות שגם הן NP-שלמות. במקום שיהיה צורך בהוכחה ישירה עבור כל אחת ואחת מהן, ניתן להשתמש בכך שידוע כי SAT היא NP-שלמה כדי להוכיח שהן NP-שלמות בעצמן בקלות רבה יותר: אם A היא בעיה שרוצים להוכיח כי היא NP-שלמה, די להראות כי ניתן לפתור את SAT בזמן יעיל אם A ניתנת לפתרון בזמן יעיל, כדי להוכיח כי גם A היא NP-שלמה.
תיאור פורמלי.
קוק הגדיר את המושג של בעיה NP-שלמה כבעיה המקיימת שני תנאים:
בצורה פורמלית ניתן להסתכל על בעיות הכרעה כבעיות של זיהוי שפה פורמלית. כך ניתן לנסח את בעיית SAT בתור הבעיה של זיהוי השפה הבאה: שפת כל הפסוקים הלוגיים בצורת CNF (כלומר בצורה קנונית קוניוקטיבית), שישנה השמה המספקת אותם. בלוגיקה מתמטית, פסוק של תחשיב פסוקים נחשב בעל השמה מספקת אם ישנה הצבה כלשהי של ערכי אמת במשתנים שלו, כך שהפסוק מקבל ערך אמת.
משפט קוק אומר כי בעיית זיהוי שפה זו היא NP-שלמה.
משמעות המשפט היא שאם ניתן לפתור את SAT בזמן ריצה פולינומי (כלומר באופן יעיל), אז ניתן להכריע את כל הבעיות שבמחלקת הסיבוכיות NP בזמן פולינומי, דבר שיגרור את השוויון P=NP.
ההוכחה פתחה פתח להוכחה מיידית כי עשרות בעיות אחרות הן NP-שלמות (בפרט מפורסם המאמר על 21 הבעיות ה-NP שלמות של קארפ מאת ריצ'רד קארפ שפורסם שנה אחרי משפט קוק). על עבודתו זכה קוק בפרס טיורינג.
עד היום, לא נמצא אף אלגוריתם פולינומי לאף אחת מהשפות הנ"ל, והשאלה האם P=NP נותרה אחת השאלות הפתוחות העמוקות במדעי המחשב.
גובי-אלטאי
גובי-אלטאי (במונגולית: Говь-Алтай аймаг) הוא השני בגודלו מבין 21 האיימאגים (מחוזות) של מונגוליה - רק מחוז אומנוגובי גדול ממנו. האיימאג ממוקם במערב המדינה ובירתו היא אלטאי.
דרך צ'רינג קרוס
דרך צ'רינג קרוס (באנגלית: Charing Cross Road) היא דרך ראשית בלונדון שבאנגליה. הדרך יוצאת מכיכר טרפלגר צפונה, לעבר כיכר סנט ג'יילס (מפגש רחוב אוקספורד עם דרך טוטנהם קורט). הדרך נקראת כך משום שהיא מובילה מצ'רינג קרוס.
היסטוריה.
הדרך הראשונה שנבנתה באתר הוקמה על ידי המלך אדוארד הראשון, על בסיס שביל שהיה במקום, בו עבר ארונה של אשתו אלינור מקסטיל במסע הלווייתה בדרך למנזר וסטמינסטר.
הדרך פותחה על ידי רשות העבודות המטרופולינית, במהלך שיפוצים שבוצעו בשדרות שפסבורי, בתקופה הוויקטוריאנית במטרה לשפר את דרכי הגישה למרכז לונדון. פיתוח הדרך נעשה מכוח חוק של הפרלמנט הבריטי משנת 1877 שהקצה 778,238 ליש"ט למטרה זו.
דרך צ'רינג קרוס ידועה בחנויות הספרים הרבות והגדולות, לספרים חדשים ולספרים מיד שנייה, שנמצאות לאורכה, ובהן:
השפעת הדרך על התרבות.
ספרות וקולנוע.
הספר "דרך צ'רינג קרוס 84" שנכתב על ידי הלין הנף, והפך לסרט קולנוע בשנת 1986 (בהשתתפות אן בנקרופט ואנתוני הופקינס) מתאר התכתבות של הסופרת עם חנות ספרים ברחוב זה, על אף שכיום כבר אין בבניין מספר 84 חנות ספרים - אלא סניף של רשת פיצה האט.
ברחוב ממוקם גם הפונדק הקלחת הרותחת שמופיע בסדרת הספרים הארי פוטר של הסופרת ג'יי קיי רולינג.
כמו כן מוזכר הרחוב בשיר "Home For A Rest" של הלהקה הקנדית "ספיריט אוף דה וסט":
"We arrived in December/And London was cold/We stayed in the bars/Along Charing Cross Road."
פיסול.
בקצה הדרומי של דרך צ'רינג קרוס נמצא פסלה של אדית קוול.
צ'רינג קרוס
צ'רינג קרוס (באנגלית: Charing Cross) הוא אזור ברובע וסטמינסטר, במרכז לונדון שבאנגליה. מקור השם הוא כפר קטן שהיה במקום זה בשם צ'רינג קרוס.
מקורו של שם הכפר שנוי במחלוקת. הכפר ידוע בכך שבו נבנתה האחרונה באנדרטאות הזיכרון למלכה אלינור מקסטיל, אשתו של המלך אדוארד הראשון. המלכה נפטרה במחוז לינקולנשייר והובאה משם למנזר וסטמינסטר במסע שנמשך שלושה עשר ימים ושנים עשר לילות. בכל שנים עשר המקומות שבהם נח ארונה של המלכה בנה המלך אדוארד הראשון צלבי זיכרון שנקראו מאז צלבי אלינור. מקום מנוחת הארון האחרון לפני לוויית המלכה היה בצ'רינג. מתוך צלבים אלה נותרו עד ימינו שלושה.
יש הגורסים שהמקום קרוי על שם הצלב, ומקורו במשפט הצרפתי "שר רין" - "מלכה אהובה". לפי גרסה אחרת, מקור השם הוא מילה אנגלית עתיקה שמשמעה "עיקול הנהר".
אנדרטת הצלב הנוכחית העומדת מול תחנת הרכבת של צ'רינג קרוס היא שיחזור ויקטוריאני של הצלב המקורי (אף שרבים חושבים ששחזור זה מעוטר יותר מהמקור). השחזור תוכנן על ידי האדריכל אדוארד מילטון בארי.
כל המרחקים בלונדון נמדדים מצלב זה.
תחנת הרכבת של צ'רינג קרוס מאוזכרת בכמה מסיפורי שרלוק הולמס.
צלבי אלינור
צלבי אלינור (אנגלית: Eleanor cross) הם אנדרטאות בצורת צלב שהוקמו על ידי המלך אדוארד הראשון מאנגליה, לזכרה של אשתו אלינור מקסטיליה . המלכה אלינור נפטרה בשנת 1290 במחוז לינקולנשייר והובאה במסע שנמשך שלושה עשר ימים ושנים עשר לילות מהארבי במחוז לינקולנשייר למנזר וסטמינסטר. בכל שנים עשר המקומות בהם נח ארונה של המלכה בנה המלך אדוארד הראשון את האנדרטאות.
שתים עשרה האנדרטאות.
מצלבים אלה שלושה שרדו: וולת'ם קרוס, נורת'המפטון וגדינגטון.
בצ'רינג קרוס נמצא שיחזור של הצלב המקורי שעמד במקום.
פסיכותרפיה
פְּסִיכוֹתֵרַפְּיָה (הלחם בסיסים שמקורו ביוונית: פסיכו - נפש, תרפיה - טיפול) הוא טיפול במשברים, בהפרעות ובמצוקות נפשיות באמצעים שונים אשר חלקם הם מפירות הפסיכולוגיה. רוב שיטות הטיפול נעשות באמצעות קשר מילולי בין המטפל למטופל. כלל המטפלים המציעים פסיכותרפיה ושמותרים על פי חוק לעסוק בה במדינתם, נכנסים בהגדרה הרחבה של "פסיכותרפיסטים".
תמיכה מחקרית.
התמיכה המחקרית החזקה ביותר לאפקטיביות של טיפול יכולה להתקבל בניסויים עם סמיות כפולה. בניסויים כאלה, החוקרת וגם המטופלת לא יודעות אם המטופלת קיבלה את הטיפול הפעיל או טיפול מסוג פלצבו. שיטת מחקר זו נפוצה בהערכה של טיפולים תרופתיים, אך פחות נפוצה בהערכה של טיפולים פסיכולוגיים. במחקר מטא-אנליזה משנת 2003 נמצא שכאשר יוצרים פלצבו אמין לטיפול פסיכולוגי, הפער באפקטיביות בינו לבין הטיפול קטן מאוד ואף זניח. תוצאות דומות נמצאו במחקר מטא-אנליזה משנת 2015 שבחן טיפול פסיכולוגי לחולים בדיכאון. כאשר השוו בין פסיכותרפיה לבין היעדר טיפול בכלל, נמצא אפקט טיפולי גדול. אך כאשר השוו פסיכותרפיה לקבוצת ביקורת שקיבלה טיפול אחר (פלצבו פסיכולוגי, פלצבו תרופתי, טיפול כרגיל), האפקט היה קטן עד שולי.
אפקטיביות טיפולית יכולה להשתנות בהתאם לסוג ההפרעה ולסוג הטיפול. מחקר מטא-אנליזה משנת 2014 בחן 101 מחקרים שכללו מעל 14,000 מטופלים הסובלים מחרדה חברתית. במחקר השוו בין טיפול פסיכולוגי לבין הימצאות ברשימת המתנה. אפקטים גדולים נמצאו לטיפולים תרופתיים, לטיפולים קוגניטיביים-התנהגותיים ולקבוצות לעזרה עצמית. לטיפול פסיכודינמי נמצאה אפקטיביות נמוכה יותר. במחקר מטא-אנליזה שהשווה טיפולים שונים לפסיכוזה, טיפול קוגניטיבי-התנהגותי נמצא הכי יעיל להפחתת תסמינים חיוביים (לדוגמה, הלוסינציות ודלוזיות) ואימון בכישורים חברתיים נמצא הכי יעיל להפחתת תסמינים שליליים (לדוגמה, אנהדוניה ושטיחות רגשית). מחקר מטא-אנליזה משנת 2014 בחן 92 מחקרים על קרוב ל-7,000 חולים המאובחנים בדיכאון. בקרב אלה שקיבלו טיפול פסיכולוגי, 62% כבר לא עמדו בקריטריונים לאבחון בסיום הטיפול. עם זאת, גם בקרב חולים שהיו בקבוצת הביקורת, רבים לא היו מאובחנים עם חלוף הזמן (43%) וגם בקרב חולים שהמשיכו את חייהם כרגיל (48%). מכאן עולה שתועלת הטיפול, מעבר לזמן שחולף, אינו גדול. נערך גם מחקר מטא-אנליזה על 52 מחקרים שהשוו שיטות פסיכותרפיה שונות לילדים ומתבגרים הסובלים מדיכאון. במטא-אנליזה נמצא שטיפול בינאישי וטיפול קוגניטיבי-התנהגותי היו אפקטיביים יותר משאר הטיפולים. טיפול במשחק וטיפול פסיכודינמי היו אפקטיביים פחות משאר הטיפולים. יתרה מכך, הם לא היו יותר אפקטיביים מאשר הימצאות ברשימת המתנה.
הסמכה והיתר לעסוק בפסיכותרפיה בישראל.
בישראל, פסיכותרפיסטים הם בדרך כלל פסיכולוגים, פסיכיאטרים, עובדים סוציאליים, קרימינולוגים, או מטפלים באמצעות אמנויות, שהם מותרים בידי משרד הבריאות לעסוק בפסיכותרפיה, בהתמחות או בהכשרה ממוקדת כאשר הכשרות כאלה לרוב מוצעות גם לעוסקים במדעי המוח, ורופאים שאינם פסיכיאטרים. העוסקים בפסיכותרפיה שאינם נמנים עם הנזכריםהם כאלו שהותרו בהיתר זמני להעניק טיפולים נפשיים בגישה קונבנציונלית בלבד ותחת פיקוח והדרכה מצד איש מתחום בריאות הנפש (בדרך כלל, פסיכולוג מומחה בכיר), הפועל תמיד מטעם משרד הבריאות. עם זאת, בהיעדר הסכמה בעולם המערבי, כמו גם בישראל, באשר להגדרת גבולות העיסוק בפסיכותרפיה, אין איסור חוקי על כל אדם להעניק טיפול פסיכותרפי, כל עוד הוא אינו יוצר מצג שווא של היותו מטפל מוסמך.
פסיכותרפיה הניתנת על ידי פסיכולוג, ככלל מהווה חלק מייעוץ פסיכולוגי, וזו הניתנת מפסיכיאטר מהווה חלק מייעוץ פסיכיאטרי. חלק מהפסיכולוגים המטפלים הם פסיכולוגים מומחים אם כי אין הכרח חוקי שפסיכולוג מטפל יתמחה בתחום מסוים ואפשר שהסמכתו הטיפולית תהיה ממוקדת או נוגעת לתחום מומחיות מוכר, שטרם זכה לתוכנית התמחות מסודרת בישראל.
חוק העובדים הסוציאליים, מתיר עיסוק בפסיכותרפיה לעובדים סוציאליים, כל עוד מטרת הטיפול היא "שיפור תפקודם האישי והחברתי של הפרט, המשפחה והקהילה".
גישות ושיטות טיפול.