stanford-oval/wikipedia huggingface dataset:
בעיית הפצת מפתחות
הגדרה פורמלית של ביטחון פרוטוקול שיתוף מפתח

אליס ובוב מעוניינים לשתף ביניהם מפתח הצפנה סודי באמצעות פרוטוקול שיתוף מפתח  \Pi . פרמטר ראשון שעליהם להסכים הוא  1^{n} (אורך המפתח בסיביות). כל אחד מהם מטיל מטבע במספר הפעמים הדרוש כדי לייצר מחרוזת אקראית באורך  n ומריץ את הפרוטוקול בערוץ פתוח שנתון לציתות. בגמר הפרוטוקול אליס ובוב מפיקים מפתחות הצפנה סודיים  k_{A},k_{B}\in \{0,1\}^{n} בהתאמה. ולצורך הנכונות, הפרוטוקול הסתיים בהצלחה אם  k_{A}=k_{B} בכל הטלת מטבעות והרצה של הפרוטוקול. במילים אחרות אליס ובוב כעת משתפים ביניהם מפתח סודי, כאשר בהגדרה המצותתת איב לא תוכל לנחש בזמן פולינומי מהו מתוך התבוננות במהלכי הפרוטוקול.
ביטחון הפרוטוקול מוגדר במונחים של ניסוי אותו אפשר לתאר בקיצור:  {\text{KE}}_{{\mathcal {A}},\Pi }^{\text{eav}}(n).
הסבר: אליס ובוב מריצים את הפרוטוקול  \Pi  בנוכחות איב (eavesdropper) המצותתת להם ומסומנת בקיצור  {\text{eav}} כשבידי כל אחד מהם מחרוזת סיביות אקראית בגודל  1^{n}. תוצאת הרצת הפרוטוקול היא עותק המכיל את מהלכי הפרוטוקול והמסרים שעברו מצד לצד וכן מפתח  k המשותף לשני הצדדים. לצורך הניסוי מטילים מטבע, דהיינו בוחרים סיבית אקראית  b\in \{0,1\} ובודקים:
אם  b=0, בוחרים מחרוזת  k'\leftarrow \{0,1\} באופן אקראי ואחיד.
אם  b=1 אזי מציבים  k'=k.
נניח שקיים אלגוריתם  {\mathcal {A}} שמקבל כקלט עותק של מהלכי הפרוטוקול  \Pi  ואת הסיבית  k' ומפיק את  b'. תוצאת הניסוי מוגדרת '1', דהיינו האלגוריתם הסתיים בהצלחה אם  b'=b אחרת התוצאה היא אפס.
פרוטוקול שיתוף מפתח  \Pi  ייקרא בטוח בנוכחות המצותתת איב, אם עבור כל  {\mathcal {A}} - אלגוריתם הסתברותי פולינומי, קיימת 'פונקציית זניחות' של  n המסומנת בקיצור  {\text{negl}}(n) כך שמתקיים:
כלומר ההסתברות ש- {\mathcal {A}} יחזיר את  b ובכך יאפשר ליריב לגלות האם  k'=k, גדולה מחצי בשיעור שאינו עולה על פונקציה זניחה כלשהי של  n. פונקציית זניחות יכולה להיות למשל מהצורה  2^{-{\text{log }}n}.
ראו גם

פרוטוקול דיפי-הלמן
MQV
שידור מוצפן
הצפנה סימטרית עם מפתח משותף
הצפנה א-סימטרית
חתימה דיגיטלית
בכחוס החולה

| --- | --- |

 מידע כללי
 צייר:  קאראווג'ו
 תאריך יצירה:  1592 לערך
 טכניקה וחומרים:  שמן על בד
 ממדים בס"מ
 רוחב:  53 ס״מ 
 גובה:  67 ס״מ 
 נתונים על היצירה
 זרם אמנותי:  Italian Baroque painting 
 מספר יצירה:  534 (גלריה בורגזה) 
 מיקום:  גלריה בורגזה, רומא
 
בכחוס החולה (באיטלקית: Bacchino Malato) הוא ציור שמן מסוג דיוקן עצמי של הצייר קאראווג'ו שצויר בין השנים 1592–1593. הדיוקן מוצג כיום בגלריה בורגזה שברומא ומכונה גם דיוקן עצמי כבכחוס (האל הרומי האחראי בין השאר על היין והגפן).
הציור צויר על ידי קאראווג'ו בשנותיו הראשונות לאחר הגעתו לרומא ממילאנו - בשנת 1592. באותה תקופה היה קאראווג'ו חולה מאוד, והיה מאושפז למעלה מחצי שנה בבית החולים סנטה מריה דלה קונסולאציונה, שם צייר קאראווג'ו מספר ציורים שלא נשמרו.
הדוגמן בציור הוא ידידו הטוב של קאראווג'יו - מריו מיניטי.
יצירה זו הגיעה לאוסף של ג'וזפה צֶ'זרי ונרכשה על ידי אספן האמנות הקרדינל שיפיונה בורגזה בשנת 1607 יחד עם נער מקלף פרי ונער עם סל פירות.
ציור אוטוביוגרפי זה שימש את קאראווג'ו כפרסומת, המציגה את יכולתו לצייר הן טבע דומם, הן דיוקנאות והן ציורים של דמויות מיתולוגיות. זווית הראש של הדמות - 3/4 ממנה מופנה לצופה - אופיינית לציור מתקופת הרנסאנס, אולם ייחודה של התמונה בזווית הראש ובעווית בה היוצרת הרגשה של סבל.
ציור זה מושווה לרוב ל"נער עם סל פירות" בו מצבם של הפירות טוב יותר - דבר המעיד על מצבו הפיזי, הנפשי והכלכלי הטוב יותר של קאראווג'ו בעת ציירו את המאוחר מבין הציורים. ציור זה מזכיר גם את הנער ב"נער הננשך על ידי לטאה".
הנדלובה

הנדלובה (בסלובקית: Handlová, בגרמנית: קריקרהאו – Krickerhau, בהונגרית: נייטרבאניה – Nyitrabánya) היא עיירה בנפת פרייבידזה, מחוז טרנצ'ין שבמרכז סלובקיה.
גאוגרפיה

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

העיירה הוקמה בשנת 1376 על ידי מתיישבים גרמנים בכתב היתר של לאיוש הראשון, מלך הונגריה. בתחילה חיו המתיישבים רק מגידולים וחקלאות, אך במאה ה-18 החלה כריית פחם באזור, שמטרתה הייתה לספק את צרכיה של טירת בויניצה (אנ') הסמוכה.
בשנת 1945, לאחר מלחמת העולם השנייה, עברה הנדלובה את המהפך הגדול ביותר בהיסטוריה שלה. רוב תושביה הגרמנים גורשו מהעיירה בעקבות הצווים שהוציא נשיא צ'כוסלובקיה אדווארד בנש, ומתוך 12,800 התושבים שחיו בהנדלובה עד 1943, רק 4,000 נותרו בה עד 1945. כתוצאה מכך השתנה אופיו של היישוב, והוא קיבל תואר עיירה רק ב-1960.
בשנת 2009, בעקבות פיצוץ במכרה סמוך לעיר (אנ'), נהרגו 20 בני אדם.
ב-15 במאי 2024 בוצע מול בית התרבות בעיר ניסיון התנקשות בראש ממשלת סלובקיה רוברט פיצו, שנורה לאחר ישיבת ממשלה. הוא הובהל לבית החולים בעיר ולאחר מכן לבית החולים רוזוולט בבאנסקה ביסטריצה, שם עבר ניתוח וניצלו חייו.
ספורט

בעיר קבוצת כדורסל, באניק הנדלובה (אנ'), המשחקת בליגת העל הסלובקית בכדורסל.
אישים

מרטין שקרטל, כדורגלן
ערים תאומות

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

↑  Handlová’s changing fortunes, SME, ‏27 בספטמבר 2010
↑  תיעוד: מתנקש ירה 5 פעמים לעבר ראש ממשלת סלובקיה, שנאבק על חייו, באתר ynet, 15 במאי 2024
↑  גיא אלסטר‏, ר"מ סלובקיה יצא מסכנת חיים: "ניסיון ההתנקשות - על רקע פוליטי", באתר וואלה, 16 במאי 2024
| --- | --- |
בקרת זהויות :  GND: 4073811-5  MusicBrainz: 8a3dcba1-11eb-4124-b726-07b92c4236ab  NKC: ge129229  VIAF: 239003078   WorldCat (עם VIAF): 239003078
הינדי

| --- | --- |

 מדינות:  הודו
 אזורים:  מזרח אסיה
 דוברים:  כ-480 מיליון
 שפת אם:  כ-250 מיליון
 כתב:  דוונאגרי
 משפחה:  הודו-אירופית הודו-איראנית הודו-ארית הינדי (מרכזית) הינדי מערבית הינדוסטאנית קהאריבולי הינדי
 לאום:  הודו הודו פיג'י פיג'י
 מוסד:  הדריקטריון ההינדי המרכזי
 קוד שפה:  hi 
 קוד ISO 639-1:  hi 
 קוד ISO 639-2:  hin 
 קוד ISO 639-3:  hin 
 ראו גם:  שפה • כתב • רשימת שפות
 
הִינְדִי (हिन्दी; ידועה גם כהינדית ולעיתים מכונה הודית) היא שפה מקבוצת השפות ההודו-איראניות במשפחת השפות ההודו-אירופיות. ההינדי היא השפה המדוברת ביותר בהודו, ואחת מן השפות המדוברות ביותר בעולם. כ-250 מיליון איש בהודו מגדירים את ההינדי כשפת אמם. בעיקר במדינות מאדהיה פרדש, ואוטר פרדש וכן בבירה דלהי. אך קשה מאוד לאמוד מספר מדויק עקב הניבים הרבים והשונים. השפה התפתחה מפראקריט (ניב אזורי) של הסנסקריט מעורב בפרסי (שפה פרסית של ראשית ימי הביניים שהגיעה עם הכובשים המוסלמים).
מעמד השפה

הסעיף ה-17 בחוקה הפדרלית של הודו עוסק במעמד הרשמי של ההינדי בתוך הקהילייה ההודית. בחוקה מפורט כיצד תפקידו של האיחוד הוא לקדם את פריסת השפה בכל רחבי המדינה, ולפתח אותה כך שהיא תיתפס כאמצעי ביטוי ייחודי בכל המרחב התרבותי של הודו, ומדוע על הממשלה הפדרלית לשמור על צביון השפה והעושר המיוחד שלה. החזון הראשוני של הממשלה הפדרלית שההינדי תהיה השפה הרשמית היחידה בהודו עד שנת 1965, אך חזון זה נתקל בהתנגדות רבה מצד תושבי הודו שהינדי אינה שפת אמם, בייחוד באזור הדרום (טאמיל נאדו למשל, ראה המחאות בטאמיל נאדו כנגד השפה ההינדית). בעקבות ההתנגדות החליטה הממשלה להנהיג את ההינדי יחד עם האנגלית.
האנגלית, שהייתה שפת השלטון בהודו בתקופה הקולוניאלית, שימשה ועדיין משמשת את מערכת בתי המשפט במדינה. עם זאת, ההינדי משמשת כמאחדת ברוב התחומים הפדרליים כיום. האזרח ההודי הממוצע לומד כיום לשוחח בשלוש שפות: הינדי, אנגלית ושפת המחוז בו הוא חי.
עד היום, מעמד ההינדי נשאר במחלוקת והוא נידון בבתי משפט. ב-2010 בית המשפט בגוג'ראט קבע כי ההינדי אינה יכולה להיות מוגדרת כשפה הרשמית היחידה בהודו, מפני שהחוקה לא מזכירה זאת באופן נחרץ.
היסטוריה של השפה

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

↑  על-פי מפקד האוכלוסין בהודו
| שפות רשמיות בהודו |
| --- | --- | --- |
| ברמת האיחוד | הינדי • אנגלית |  |
| ברמת המדינות | אורדו • אורייה • אסאמית • בודו • בנגלית • גוג'ראטית • דוגרית • הינדית • טלוגו • טמילית • מאיטהילית • מלאיאלאם • מניפורית • מראטהית • נפאלית • סינדית • סאנטלית • סנסקריט • פנג'אבי • קונקאני • קאנדה • קשמירית |  |
| שפות קלאסיות | טלוגו • טמילית • סנסקריט • קאנדה |  |
| ראו גם | שפות הודו-איראניות • שפות הודו-אירופיות • שפות דראווידיות • הודו: שפות |  |
| שפות הודו-אירופיות |
| --- | --- | --- |
| שפות רומאניות | צרפתית • מונגאסקית • ארפיטנית • ולונית • אוקסיטנית • גסקונית • אראנית • קטלאנית • ספרדית • לאדינו • חכיתיה • גליסית-פורטוגזית • פורטוגזית • גליסית • אסטור-לאונית • אסטורית • לאונית • מירנדזית • איטלקית • קורסיקאית • ליגורית • נפוליטנית • סיציליאנית • סרדינית • איסטרית • פריאולית • לדינית • רומאנש • דלמטית • רומנית • מולדובנית • ארומנית • איסטרו-רומנית | בירוק כהה: מדינות עם רוב דובר שפות הודו-אירופיות. בירוק בהיר: מדינות עם מיעוט דוברי שפות הודו-אירופיות שקיבלו הכרה רשמית |
| שפות גרמאניות | אלמאנית • אלזסית • גרמנית שווייצרית • גרמנית • לוקסמבורגית • בווארית • ריפוארית • סקסונית עילית • יידיש • הולנדית • אפריקאנס • לימבורגית • סקסונית • זיילנדית • פריזית • סקוטית • אנגלית • דנית • שוודית • נורווגית ספרותית • איסלנדית • פארואזית • נורווגית חדשה | בירוק כהה: מדינות עם רוב דובר שפות הודו-אירופיות. בירוק בהיר: מדינות עם מיעוט דוברי שפות הודו-אירופיות שקיבלו הכרה רשמית |
| שפות סלאביות | אוקראינית • בלארוסית • רוסית • רוסינית • סלובקית • צ'כית • פולנית • פומרנית • קשובית • סורבית עילית • סורבית תחתית • בולגרית • מקדונית • סרבית • קרואטית • סלובנית • בוסנית • שלזית | בירוק כהה: מדינות עם רוב דובר שפות הודו-אירופיות. בירוק בהיר: מדינות עם מיעוט דוברי שפות הודו-אירופיות שקיבלו הכרה רשמית |
| שפות קלטיות | ברטונית • ולשית • קורנית • גאלית סקוטית • אירית • שלטה | בירוק כהה: מדינות עם רוב דובר שפות הודו-אירופיות. בירוק בהיר: מדינות עם מיעוט דוברי שפות הודו-אירופיות שקיבלו הכרה רשמית |
| שפות הודו-איראניות | סנסקריט • אסאמית • בנגלית • גוג'ראטית • הינדי • מאיטהילית • מראטהית • נפאלית • אורייה • פאלי • פנג'אבי • רומאני • סינדית • סינהלית • אורדו • דיבהי • דאמלי • דומאקי • גאוואר-באטי • קאלאשה • קשמירית • חוואר • קוהיסטנית • ניגאלאמית • פאשאי • פאלורה • שינה (שפה) • שומשתי • אשקום • קמוירי • קאטי (באשגלי) • פרסואנית (ווסי-וורי) • טרגמי • וואיגלית (קאלאשה-אלה) • פרסית • פאהלוי ("פרסית תיכונה") • פשטו • דארי של אפגניסטן • טג'יקית • אוסטית • כורדית • באלוצ'י • טאליש • טאטית • ג'והורי • ג'יהדי • דארי של זורואסטריאן • יאגנובי | בירוק כהה: מדינות עם רוב דובר שפות הודו-אירופיות. בירוק בהיר: מדינות עם מיעוט דוברי שפות הודו-אירופיות שקיבלו הכרה רשמית |
| שפות בלטיות | לטבית • ליטאית | בירוק כהה: מדינות עם רוב דובר שפות הודו-אירופיות. בירוק בהיר: מדינות עם מיעוט דוברי שפות הודו-אירופיות שקיבלו הכרה רשמית |
| אחר | יוונית • אלבנית • ארמנית | בירוק כהה: מדינות עם רוב דובר שפות הודו-אירופיות. בירוק בהיר: מדינות עם מיעוט דוברי שפות הודו-אירופיות שקיבלו הכרה רשמית |
| --- | --- |
בקרת זהויות :  NLI: 987007560449805171  BnF: cb11932019c (data)  GND: 4024954-2  LCCN: sh85060875  NDL: 00563236  NKC: ph120700  TDVİA: hint-uslubu 
ערך זה הוא קצרמרבנושא שפות ובנושא הודו. אתם מוזמנים לתרום לוויקיפדיה ו.
בראיין טיילור

| --- | --- |

טיילור בשנת 2010
 לידה:  9 ביוני 1951 (בן 73) פרת' אמבוי, ניו ג'רזי, ארצות הברית
 עמדה:  רכז
 גובה:  1.88 מטרים
 מספר:  14
 מכללה:  אוניברסיטת פרינסטון
 דראפט:  בחירה מספר 23, 1972 סיאטל סופרסוניקס
 קבוצות כשחקן
 1972–1976 1976–1977 1977–1978 1978–1982:  ניו יורק נטס קנזס סיטי קינגס דנוור נאגטס סן דייגו קליפרס
 הישגים כשחקן
 ב-ABA: 2 זכיות באליפות (1974, 1976) 2 בחירות למשחק האולסטאר (1975, 1976) החמישייה השנייה של העונה (1975) 2 בחירות לחמישיית ההגנה של העונה (1975, 1976) זכייה בפרס רוקי העונה (1973) ב-NBA: חמישיית ההגנה השנייה של העונה‏ (1977)
בראיין דווייט טיילור (באנגלית: Brian Dwight Taylor; נולד ב-9 ביוני 1951) הוא כדורסלן עבר אמריקאי, אשר שיחק בליגות ה-ABA וה-NBA בין השנים 1972–1982. ממוצעיו הכוללים לאורך 10 עונותיו בשתי הליגות הם 13.1 נקודות, 4.1 אסיסטים, 2.7 ריבאונדים ו-2.1 חטיפות למשחק.
קריירת משחק

טיילור נולד וגדל בעיר פרת' אמבוי שבניו ג'רזי, ובין השנים 1969–1972 למד באוניברסיטת פרינסטון. בשתי עונותיו בקבוצת הכדורסל של האוניברסיטה הצטיין עם ממוצע של 24.3 נקודות למשחק, תחת המאמן חבר היכל התהילה של הכדורסל פיט קאריל.
קריירת משחק > ב-ABA

בדראפט ה-NBA‏ 1972 נבחר טיילור בבחירה ה-23 על ידי סיאטל סופרסוניקס, אך הוא בחר לשחק בקבוצת ניו יורק נטס מליגת ה-ABA. בעונתו הראשונה בליגה קלע טיילור 15.3 נקודות בממוצע למשחק, ובסיומה זכה בפרס רוקי השנה של ה-ABA. בעונה העוקבת זכה עם הנטס באליפות הליגה, כאחד השחקנים הבולטים בקבוצה לצדם של ג'וליוס ארווינג, לארי קינון ובילי פולץ. בעונת 1974/1975 הוביל את כל שחקני הליגה עם ממוצע של 2.8 חטיפות למשחק, השתתף במשחק האולסטאר של ה-ABA ונבחר לחמישיית ההגנה של העונה, ובעונה שלאחריה הוביל את הליגה באחוזי קליעה לשלוש, עם 42.1%, ונבחר בשנית הן למשחק האולסטאר והן לחמישיית ההגנה. בסדרת הגמר של עונת 1976 גברו הנטס על דנוור נאגטס בתוצאה 4–2, ובכך זכו באליפות העונה האחרונה בתולדות ליגת ה-ABA. במשחק השישי והאחרון של הסדרה קלע טיילור 24 נקודות, וסייע לקבוצתו לחזור מפיגור של 14 נקודות ברבע האחרון לניצחון בתוצאה 112–106.
קריירת משחק > ב-NBA

בקיץ 1976 עבר יחד עם הנטס לליגת ה-NBA, אך לפני תחילת עונת 1976/1977 נשלח לצד ג'ים איקינס ושתי בחירות דראפט עתידיות בטרייד לקנזס סיטי קינגס, תמורת נייט ארצ'יבלד. בעונתו היחידה עם הקינגס קלע שיא קריירה של 17.0 נקודות בממוצע למשחק.
לקראת עונת 1977/1978 הועבר בטרייד לדנוור נאגטס, אותה אימן לארי בראון. באותה עונה קלע 11.6 נקודות למשחק, וסייע לנאגטס להעפיל לגמר האזור המערבי בפלייאוף.
בפברואר 1982 חתם על חוזה בקבוצת סן דייגו קליפרס, לקראת עונתה הראשונה בסן דייגו לאחר המעבר מבאפלו. בעונת 1979/1980, בה הוסיפה ליגת ה-NBA את קשת השלוש, הוביל טיילור את כל שחקני הליגה בזריקות ובקליעות לשלוש, עם 90 שלשות מתוך 239 ניסיונות זריקה. בעונה העוקבת הוביל את הליגה באחוזי קליעה לשלוש, עם 38.3%. בפברואר 1982 סבל טיילור מקרע בגיד אכילס, ונאלץ לפרוש ממשחק, בגיל 30 בלבד.
הערות שוליים

1 2  סטטיסטיקות הקריירה של טיילור ב-ABA וב-NBA, באתר basketball-reference.com
↑  סטטיסטיקות המכללות של טיילור, באתר sports-reference.com
↑  רשימת הנבחרים בדראפט 1972, באתר basketball-reference.com
↑  סטטיסטיקות המשחק בין הנטס לנאגטס, באתר basketball-reference.com
↑  טיילור נשלח בטרייד לקינגס, באתר הניו יורק טיימס, 11 בספטמבר 1976
↑  טיילור חוזר לפרינסטון בגיל 31, באתר ניו יורק טיימס, 4 במאי 1983
בעיית הספיקות

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

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

מקובל להתייחס בשם  k{\text{-SAT}} לבעיית סיפוק נוסחאות בצורת CNF אשר כל הפסוקיות המופיעות בהן מאורך  \ k. ניתן לראות כי הבעיות  1{\text{-SAT}} ו \ 2{\text{-SAT}} ניתנות לפתרון בזמן פולינומי. (כלומר, שייכות ל-P), בעוד שעבור  \ k\geq 3 הבעיה המתקבלת ‏NP-שלמה (כלומר, צמצום הבעיה לפסוקיות מאורך  \ k בלבד לא הופך אותה לקלה יותר)
בעזרת למת המקומיות של לובאס ניתן להראות כי אם כל משתנה מופיע בלכל היותר  2^{k}/4k פסוקיות, אזי קיימת השמה מספקת. מאידך, ייתכן כי לא ניתן למצוא את ההשמה המספקת בזמן פולינומי.
בעיות אופטימיזציה נגזרות

בהינתן נוסחת CNF בעלת  \ m פסוקיות, ניתן לשאול מה מספר הפסוקיות המקסימלי אשר ניתן לספק באמצעות השמת ערכי אמת. (אם הנוסחה ספיקה, מספר זה הוא  \ m) בעיה זו מכונה בעיית ספיקות מקסימלית. (באנגלית, Max-Sat) ניתן להוסיף ולהכליל בעיה זו באמצעות קביעת משקל  \ w_{i} לכל פסוקית, ומציאת השמת ערכי אמת עבורה משקל הפסוקיות המסופקות יהיה מקסימלי. גרסה זו של הבעיה נקראת בעיית הספיקות המשוקללת המקסימלית. (באנגלית Max-W-Sat)
נמצאו אלגוריתמי קירוב רבים לבעיות אלה, אשר נותנים קירובים שונים, (1/2, 2/3, 3/4 ואף יותר מכך), אך הוכח בשנת 1997 כי לא ייתכן אלגוריתם פולינומי אשר מבטיח פתרון טוב יותר מאשר 7/8-קירוב. (אלא אם כן P=NP) לכן, שייכות הבעיות Max-Sat ו-Max-W-Sat למחלקה APX אך לא ל-PTAS. (אלא אם כן, P=NP, ואז שתי המחלקות הנ"ל שוות)
ראו גם

חיפוש מקומי
הערות שוליים

↑  D.S. Johnson, Approximation algorithms for combinatorial problems, journal of Computer and System Sciences 9 (1974), pp. 256-278
↑  J. Chen, D. K. Friesen and H. Zheng, Tight bound on the Johnson’s algorithm for Max-SAT, Proc. 12th Annual IEEE Conf. On Computational Complexity (1997), Ulm, Germany, pp. 274-281
↑  M. Yannakakis, On the Approximation of Maximum Satisfiability, Journal of Algorithms 17 (1994), pp. 475-502
↑  M. X. Goemans and D. P. Williamson, New 3/4-approximation algorithms for MAX SAT, SIAM Journal on Discrete Mathematics 7 (1994), pp. 656-666
↑  J. Håstad, Some optimal inapproximability results, Proc. 28th Annual ACM Symp. on Theory of Computing (1997), El Paso, Texas, pp. 1-10
ערך זה הוא קצרמרבנושא מדעי המחשב. אתם מוזמנים לתרום לוויקיפדיה ו.
ארלט הילו

| --- | --- |
אין תמונה חופשית
 לידה:  4 ביוני 1945 (בת 79) קוריטיבה, פרנה, ברזיל ברזיל 
 מדינה:  ברזיל ברזיל
 מקום מגורים:  סאו פאולו, מדינת סאו פאולו, ברזיל
 פעילות בולטת:  סחר בתינוקות
 ידועה בשל:  הובילה כנופיה שהבריחה תינוקות וסחרה בהם באופן לא חוקי
 תקופת הפעילות:  1978 (בערך) – 1992
 השקפה דתית:  נצרות קתולית
 
ארלט הילו (בפורטוגזית: Arlete Hilu), היא אישה ברזילאית שלקחה חלק חשוב בסחר בילדים בשנות ה-70, ה-80 וה-90 במאה ה-20.
ביוגרפיה

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

הילו מכרה ילדים ברזילאים להורים ממדינות רבות בעולם. המדינה שממנה הגיעו הכי הרבה קונים לילדים היא ישראל. מספר הילדים שנמכרו על ידה מוערך בכ-3,000 ילדים.
באותה התקופה המשטרה הברזילאית הייתה אדישה לסחר בילדים ולא אכפה את החוקים. הילו חקרה את הנושא, הכירה אנשים והקימה כנופיה שסחרה בתינוקות והעבירה אותם למדינות רבות בעולם, לכאורה בתהליך של אימוץ בינלאומי.
ארלט עבדה באופן שיטתי ומסודר, וכך עבדה שיטתה של ארלט לסחור בילדים: ראשית, לקוחות היו פונים להילו ומבקשים ממנה להביא להם תינוק, מחיר תינוק היה בין 5000 ל-50,000 דולר. שנית, הייתה מחביאה הילו את התינוקות הרכים אצל חברתה לכנופיה בזמן שהיא מזייפת מסמכי אימוץ. לאחר מכן הייתה מבריחה חלק מן הילדים לפרגוואי במזוודות בתא המטען של הרכב וחלק מן הילדים הייתה מטיסה לישראל או לאזור אחר.
במהלך חודש מרץ 2017 שודר עליה ועל דרכי הפעולה של כנופייתה תחקיר רחב בתוכנית "אבודים" בו לקחו חלק ילדים שנמכרו לישראל. התחקיר נערך בישראל ובברזיל ובמסגרתו מצאה אחת מהנמכרות את אימה הביולוגית.
הערות שוליים

1 2 3  אבודים עונה 9 פרק 2 לצפייה ישירה, רשת, 22 במרץ 2017
↑  Brazil – Arlete Hilu case, PPL
↑  "Eu não sabia do tráfico de bebês", afirma mulher condenada por envolvimento no esquema de adoções ilegais, VOCÊ ESTÁ EM DIÁRIO CATARINENSE
↑  תרגום הכותרת: "קוריטיבה שיכנה פעם קבוצה של סוחרי ילדים", Curitiba já abrigou grupo de traficantes de crianças, Gazeta do Povo, ‏2011-07-16 (ב־Brazilian Portuguese)
הטבח באיילה ויסטה

| --- | --- |

 תאריך:  23 במאי 2014
 מקום:  איילה ויסטה (אנ'), קליפורניה, ארצות הברית
 קואורדינטות:  34°24′43″N 119°51′32″W﻿ / ﻿34.412°N 119.859°W﻿ / 34.412; -119.859
 סוג:  רצח המוני פיגוע דקירה פיגוע דריסה
 נשק:  שני סכינים אקדח גלוק 34 שני אקדחי זיג זאואר P226 רכב ב.מ.וו. סדרה שלוש קופה 328i
 הרוגים:  6
 פצועים:  14
 מבצע:  אליוט רוג'ר
 מספר מפגעים:  1
 מפגעים הרוגים:  1
 מניע:  מיזוגיניה
  (למפת קליפורניה מוגדלת) סקרמנטו לוס אנג'לס סן פרנסיסקו סן דייגו סן חוזה פרזנו בייקרספילד אורגון נבדה א ר י ז ו נ ה  מקסיקו האוקיינוס השקטהטבח באיילה ויסטה(למפת קליפורניה רגילה) סקרמנטו לוס אנג'לס סן פרנסיסקו סן דייגו סן חוזה פרזנו בייקרספילד אורגון נבדה א ר י ז ו נ ה  מקסיקו האוקיינוס השקטהטבח באיילה ויסטה(למפת ארצות הברית רגילה) וושינגטון ניו יורק לוס אנג'לס שיקגו סן פרנסיסקו אטלנטה דאלאס יוסטון בוסטון סיאטל מיאמי ה א ט ל נ ט י  ה ש ק ט  מפרץ מקסיקו  קנדה מקסיקו איי בהאמה הטבח באיילה ויסטה(למפת ארצות הברית מוגדלת) וושינגטון ניו יורק לוס אנג'לס שיקגו סן פרנסיסקו אטלנטה דאלאס יוסטון בוסטון סיאטל מיאמי ה א ט ל נ ט י  ה ש ק ט  מפרץ מקסיקו  קנדה מקסיקו איי בהאמה הטבח באיילה ויסטה
 
הטבח באיילה ויסטה (באנגלית: The Isla Vista Massacre) היה אירוע רצח המוני מסוג טרור מיזוגיני שהתרחש בקהילת איילה ויסטה (אנ'), קליפורניה, ארצות הברית, ב-23 במאי 2014, במהלכו אליוט רוג'ר בן העשרים ושתיים רצח שישה בני אדם ופצע ארבעה עשר נוספים באמצעות ירי מנשק חם, דקירות סכין ודריסה, בטרם התאבד. את המניע למעשיו תיאר במנשר בן מאה ושלושים ושבעה עמודים שהפיץ באופן מקוון במהלך המתקפה, בנוסף לסרטונים רבים שהעלה לערוץ היוטיוב שלו, בהם הביע את כוונתו להעניש את המין הנשי על העוול וחוסר הצדק המשווע שלטענתו נגרמו לו בשל אי קבלתו כשווה בין שווים בחברה האנושית, וכן בעקבות חוסר יכולתו למצוא בת זוג בדומה לשאר האנשים הסובבים אותו.