كيف كانت أول NP-complete مشاكل أظهرت أن تكون NP-كاملة ؟

Question

من ويكيبيديا على NP-Complete:

"أسهل طريقة لإثبات أن بعض مشكلة جديدة هي NP-complete هو أول من يثبت أنه في NP ، ومن ثم خفض بعض المعروف NP-complete مشكلة في ذلك"

أنا متأكد أن أفهم هذه:إذا كان لدي مشكلة, أنا يمكن أن تظهر أنه NP-Complete إذا كنت:

1. تظهر أنه في NP (حل المشكلة يمكن التحقق منها في متعدد الحدود على غير القطعية آلة تورينج)

2. تبين أن المشكلة بالفعل من المعروف أن NP-Complete يمكن 'تقليص' إلى مشكلة جديدة

لذا سؤالي هو: كيف كانت أول NP-complete المشاكل 'مؤكدة' أن NP-كاملة ؟ في وقت واحد مجموعة من المعروف NP-complete المشاكل يجب أن يكون صفر ، وهذا من شأنه أن يجعل من المستحيل أن تلجأ إلى الخطوة 2 في العملية المذكورة أعلاه.

هذا يجعلني أعتقد أن هناك طريقة مختلفة عن الإثبات التي لست على علم.إما هذا أو ربما كل NP-complete الملكية 'المفترض' بعض المشاكل بسبب عدم وجود معروفة وقت متعدد الحدود الحل.(في الواقع ، بعد أن كتب هذا لن يفاجأ إذا كان هذا هو الحال, ولكن أود بعض جورو-ردود الفعل في كلتا الحالتين).

Answer 1

نظرية كوك

الطبقة NP يمكن تعريفها بأنها الطبقة من المشاكل decidable من قبل غير حتمى آلة تورينج في وقت متعدد الحدود.هذا يدل على ان نظرية جلس هو NP-complete من خلال ترميز تشغيل أي غير حتمى آلة تورينج بحلول منطقية الصيغة في مثل هذه الطريقة أن الجهاز يقبل إذا وفقط إذا كانت هذه الصيغة هو قابل للإرضاء عربية.

تاريخيا, مفهوم NP-اكتمال قدم في ريتشارد كارب المنوي ورقة (Reducibility بين اندماجي مشاكل) ، حيث عرف NP-اكتمال تستخدم نظرية كوك في طلقة واحدة كبيرة ، أثبتت 21 المشاكل NP-complete.

Answer 2

لتعطيك جوهر البرهان (الذي هو عدة صفحات من الصعب الذهاب في Garey & جونسون أجهزة الكمبيوتر و Intractibility):

أي الحسابية المشكلة يمكن التعبير عن آلة تورينج.

فمن الممكن أن أعرب عن آلة تورينج المنطق مشكلة مرضية معينة تعقيد القيود.

ولذلك, إذا كنت يمكن أن تحل المشكلة منطق في وقت متعدد الحدود ، يمكنك حل آلة تورينج المشكلة في وقت متعدد الحدود.

هذا (جنبا إلى جنب مع بعض الاعتبارات الأخرى) يدل على أنه إذا كنت يمكن أن تحل المشكلة منطق في وقت متعدد الحدود ، يمكنك حل أي NP المشكلة في وقت متعدد الحدود.هذا هو تعريف NP-complete, منطق المشكلة ولذلك NP-complete, و يمكن أن تستخدم كأساس مشاكل أخرى.

منطق مشكلة المستخدمة يسمى Satisfiability (غالبا ما يختصر إلى السبت).بالنظر إلى سلسلة من بنود النموذج (أ أو ب أو ج) (بنود تتكون من أي عدد من المقترحات و والنفي من المقترحات متصلة أو المنطقي), هل هناك مهمة من القيم الحقيقة أن المقترحات التي تجعل جميع بنود صحيح ؟

NP-اكتمال واضحة المعالم الملكية.السبب الوحيد أنك تكون في شك حول المشكلة NP-complete هو الذي كنت تعتقد أنك يمكن أن تقلل من آخر NP-complete المشكلة ولكن لم أجد مريحة مشكلة أو اشتقاق دليل حتى الآن.

والسؤال هو ليس ما إذا كان NP-complete المشاكل موجودة ، أو كيفية إثبات المشكلة هي NP-complete, ولكن ماذا يعني ذلك.لا أحد لديه حتى الآن إنتاج متعدد الحدود-الوقت خوارزمية لحل NP-complete المشكلة و لا أحد أثبت أن مثل هذه الخوارزمية لا يمكن أن توجد.ما إذا كان أو لا P=NP, نحن بالتأكيد لم يكن لديك جيدة الخوارزميات لحل أي NP-complete المشكلة.

هذا هو واحد من كلايبول مؤسسة الألفية المشاكل ، لذلك إذا كنت يمكن أن تأتي مع دليل على أن تم التملص من بعض الناس مشرق جدا لسنوات قليلة جدا, هناك مليون دولار في ذلك بالنسبة لك.