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