مسئله رایانشی

مسئله تصمیم، مسئله رایانشی ای است که پاسخ هر نمونه آری یا نه است. مثالی ای از مسئله تصمیم «آزمون عدد اول» است:

«با فرض عدد صحیح مثبت n، آیا n عدد اول است»

مسئله تصمیم نوعاً به عنوان مجموعه‌ای از همه نمونه‌هایی که پاسخ آنها آری است، بازنموده می‌شود. برای مثال آزمون عدد اول می‌تواند به عنوان یک مجموعه بی پایان بازنموده شود:

L = {۲, ۳, ۵, ۷, ۱۱, ...}

مسئله بهینه‌سازی به دنبال یافتن «بهترین امکان» میان همه راه حل‌های ممکن در یک مسئله جستجو است. مثالی از مسئله بهینه‌سازی «مسئله بزرگترین مجموعه مستقل» است.

«با فرض گراف G، یک مجموعه مستقل از G با اندازه بیشینه را بیابید»