מה C מייצג? בהתחשב בשאלה הקודמת, כתוב את ההקשר שמכיל את התשובה. זה יכול להיות 1 - 20 משפטים. -הקשר:
זה מניע את המושג של בעיה קשה עבור כיתה מורכבת. בעיה X היא קשה עבור סוג של בעיות C אם כל בעיה ב- C יכולה להיות מופחתת ל- X. לכן אין בעיה ב- C קשה יותר מ- X, שכן אלגוריתם ל- X מאפשר לנו לפתור כל בעיה ב- C. כמובן, המושג של בעיות קשות תלוי בסוג של הפחתה המשמשת. עבור כיתות מורכבות גדולות מ-P, משמשים בדרך כלל הפחתת זמן פולינומי. בפרט, קבוצת הבעיות הקשות ל-NP היא קבוצת הבעיות הקשות ל-NP.