يمكن أن يحدث متعدد الحدود متعددة إلى واحد على مثيل مشكلات محددة؟

Question

دعنا نقول أنني تقلل من المشكلة $ a \ in l $ إلى $ b \ in k $ ، مع وظيفة $ f: \ sigma ^ {*} \ rawrow \ gamma ^ {*} $ مثل $ W \ في l \ leftrightrow f (w) \ in k $ . أعرف ما إذا كنت أرغب في حل $ $ ، بالنظر إلى بعض خوارزمية وقت متعدد الحدود ل $ B $ ، i يجب عليك فقط تحويل $ $ إلى $ B $ وحل $ B $ . لذلك يمكن اعتباره:

يجب أن يتم التخفيض من المثيل التعسفي من $ $ إلى مثيل قانوني من $ B $

سؤالي هو، هل يجب أن أقلل إلى التعسفي مثيل $ B $ أو بعض مثيل من $ B $ ؟ بمعنى آخر. يتم تخفيض من TQBNF إلى الجغرافيا المعممة لبعض مثيل الرسم البياني صالح، ولكن هناك العديد من مثيلات الجغرافيا المعممة.

Answer 1

التعيين ليس من الضروري أن يكون سفر (ONTO) ولا حقن (واحد إلى واحد).في الواقع، يمكن أن تكون أي مشكلة يمكن حلها في الوقت الذي يمكن حله في وقت متعدد الحدود أن يكون وقت متعدد الأصنان على أي مشكلة تحتوي على مثيل واحد على الأقل قبوله ومثيل واحد على الأقل رفض: فقط حل المشكلة الأصلية في وقت متعدد الحدود، ثم إرجاع القبولمثيل إذا كانت المشكلة الأصلية مثيل قبول، أو مثيل رفض إذا كانت المشكلة الأصلية مثيل رفض.

قال، Berman-hartmanis تخمين ينص على أن كل شيء np-complete المشاكل هي الوقت متعدد الحدود ISOMORPHIC ، وهذا يعني أن هناك حفارة وقت متعدد الحدود متعددة بينهما بينهما مع وقت متعدد الحدودمعكوس.هذا هو حاليا تخمين غير مثبت، ويشير فقط إلى مشاكل NP كاملة.