ملخص

1

الفئة P هي فئة من المشكلات التي يمكن تحديدها في وقت متعدد الحدود على آلة تورينغ الحتمية، والفئة NP هي فئة من المشكلات حيث، عند إعطاء دليل على أن الإجابة هي نعم (يسمى شاهد)، يمكن التحقق من صحة الشاهد في وقت متعدد الحدود (وهذا ما يسمى بالتحقق). نظرًا لأن المشكلات التي يمكن تحديدها في وقت متعدد الحدود يمكن التحقق منها في وقت متعدد الحدود، فمن الواضح أن P⊆NP، ولكن ليس من الواضح ما إذا كانت P مجموعة فرعية حقيقية من NP. على الرغم من عدم وجود دليل حتى الآن، يعتقد العديد من الباحثين أن P≠NP. هذا التخمين بأن الفئة P والفئة NP ليسا متساويين يسمى "تخمين P≠NP".