هو عدد NP-complete مشاكل محدودا ؟

Question

ينبغي أن يكون على التوالي إلى الأمام لإظهار أن هناك عدد لانهائي من NP-hard المشاكل:

برهان: تأخذ المشكلة إزالة 1 Vertex 3-COL ($R1V3COL$) الذي يأخذ الرسم البياني $G=(V,E)$ كمثال و ينتج بنعم المنتدى قمة الرأس $x \in V$ يوجد والتي عند إزالتها من $V$ ينتج رسم جديد $G'=(V\مائل\{x\}, \{(u,v) \E\,|\, u eq x \الأراضي v eq x\}$ وهو أمر إيجابي مثيل $3COL$.

$R1V3COL$ يمكن في الواقع أن يتم تخفيضها إلى 3 الألوان الثنائية المشكلة (التي ثبت أن تكون NP-complete) من قبل (على سبيل المثال الحد) ببساطة إزالة الرأس من $G$ والاختبار إذا $G$ 3-ملون.إذا $G$ لا 3-ملون إزالة قمة أخرى من $G$ واختباره.أكرر حتى لا توجد القمم اليسار للاختبار.

ولذلك نحن نعرف $R1V3COL$ هو NP-hard المشكلة.

ونحن الآن يمكن أن تقلل من $R2V3COL$ إلى $R1V3COL$ مشكلة (حسب مفهوم مماثل كما هو مبين أعلاه $R1V3COL$ إلى $3COL$ لإظهار أن $R2V3COL$ في NP-من الصعب على كل إزالة n القمم 3-COL المشكلة.وبعبارة أخرى يمكننا تقليل دائما $R(n)V3COL$ إلى $R(n-1)V3COL$.ولذلك نحن نعلم أنه يجب أن يكون هناك عدد لانهائي من NP-hard المشاكل و نحن القيام به.

الآن إلى ليما: لا أستطيع أن أفكر في دليل بسيط لإظهار أن مشكلة معينة مع عدد لانهائي من الاختلافات (مثل $R(n)V3COL$) هو أيضا في NP لإثبات NP-اكتمال وبالتالي تثبت بلا حدود العديد من المشاكل في فرعية-NP كاملة.

Answer 1

كما في تعليق النظر في مجموعة من المشاكل $N$-جلس (هو $\phi$, منطقية الصيغة في $N$-CNF, قابل للإرضاء عربية?).أو $N$-تلوين الرسوم البيانية ، $N \قه 3$ (يمكن أن تكون ملونة مع الرسم البياني $N$ الألوان؟).العديد من NP-complete مشاكل بعض المعلمة (هل هناك زمرة من حجم $k$ في الرسم البياني?وقد digraph ردود الفعل قمة مجموعة من حجم $k$?).

Answer 2

لكل عدد صحيح ك ، تأخذ السفر بائع مشكلة مع n > 1 المدن حيث n هو قوة k.(التقطت المشكلة بهذه الطريقة لأن كل الحالات متميزة ، لذلك يمكننا أن نقول بضمير مستريح أن هذه هي متميزة مشاكل).