يمكن للشخص يرجى إعطاء مثال عداد منه؟إذا كانت هناك مشكلة في NP، فلا توجد خوارزمية زمنية متعددة الحدود لحلها

Question

هل هناك أي خوارزمية زمنية متعددة الحدود غير معروفة لحل مشكلة في هذه المشكلة في NP.قيل لي أنها خاطئة ولكن لا يمكنك التفكير في أي مثال عداد الآن.

Answer 1

np هو فئة مشاكل القرارات حيث يكون أي مثيل مع إجابة "نعم" دليل على أن الإجابة هي نعم يمكن التحقق منها في وقت متعدد الحدود.يحتوي NP على جميع المشكلات القابلة للحل في وقت متعدد الحدود.لذلك هناك العديد من المشاكل في NP مع خوارزميات زمنية متعددة الحدود.

إذا كنت تتحدث عن مشاكل NP كاملة، فهذا أمر مختلف تماما.هناك (في هذه المرحلة الزمنية) لا مشكلة كاملة من NP مع خوارزمية وقت متعدد الحدود المعروفة لحلها.

قد يجد شخص ما دليلا على وجود مشكلة كاملة من NP لا توجد مشكلة كاملة من NP مع خوارزمية وقت متعدد الحدود لحلها - وليس فقط خوارزمية معروفة، ولكن لا allgoritm على الإطلاق.

من ناحية أخرى، قد يجد شخص ما في الواقع إكمال np-complete يمكن حلها في وقت متعدد الحدود.من غير المرجح أن.