ما الذي يحدث "إذا تم تخفيض P1 إلى P2، فإن P2 هو على الأقل صعبة مثل P1" يعني؟

Question

أواجه مشكلة في فهم العبارة التالية المتعلقة بتخفيض تورينج:

"إذا تم تخفيض P1 إلى P2، فإن P2 هو على الأقل صعبة مثل P1."

هل هذا يعني أن

(i) p2 يمكن أن يكون أصعب أو صعب مثل P1، أو (2) يمكن أن يكون P2 أسهل أو صعب مثل P1؟

لتمثيل هذا بصريا ...

سأقدر أي رؤية في هذه المسألة.شكرا لك.

Answer 1

الترجمة الشفوية (I) صحيح: " $ $ هو الأقل صعبة مثل $ B $ "يعني أن $ A $ هو صعب كما هو أو أصعب تماما من $ b $ .(فكر في الأرقام: " $ A $ هو على الأقل كبيرة مثل $ B $ " يعني " $ A= B $ أو $ a> b $ . ")

لاحظ أنه لا يفعل فقط " $ $ هو على الأقل صعبة مثل $ B $ "استبعاد $ $ كونها أضعف بشكل صارم من $ B $ ، فإنه يسيطر أيضا على $ $ و $ B $ يجري تعقيد لا تضاهى .تعقيد ليس ترتيب خطي؛يمكننا أن نجد مشاكل بحيث لا يساعدنا في حل الآخرين.