هل هناك NP-hard المشكلة التي لا ثابت-المعلمة لين العريكة خوارزمية موجود ؟

Question

السؤال

هل هناك NP-hard المشكلة التي يمكننا إضافة معلمة¹ لإنشاء "الطبيعية"² parametrised المشكلة التي لا FPT خوارزمية موجود ؟

1. إضافة معلمة مطلوب لأن NP-hard المشكلة هو عادة فقط سؤال إجابة بنعم أو لا, إذا كنت تريد أن تحد من بعض المعلمة تحتاج إلى تحديد أي واحد (على الرغم من أن شيئا مثل $k$-التلوين قد يكون واحد واضح بالفعل) ، وذلك مع "تحديد المعلمة" واحد هو تحد واحد هو "إضافة المعلمة" لهذه المشكلة.وصف أكثر تفصيلا يتم تضمينها في الإجابة المنفصلة سحلية.
2. أعتقد الطبيعية يحاول استبعاد "تافهة" parameterizations كما أناقش في أول شك في هذه المسألة.مرة أخرى أكثر تفصيلا الوصف يتم تضمينها في الإجابة المنفصلة سحلية.

شك

0. قد يكون سؤالا تافها كما أنه ربما يكون من الممكن دائما "الأشياء" المشكلة برمتها داخل $f(k_1,k_2,..,k_m)$ جزء من $f(k_1,k_2,..,k_m)ن^c$ خوارزمية أثناء الإعداد $n=c'$ حيث $c$ هو التعسفي المستمر.ولكن ربما التعريف الدقيق FPT يمنع مثل هذه (ab)استخدام مفهوم FPT.

بناء على تعليق من نزول المطر هناك في الواقع موجود تافهة طريقة parameterize "أي" (أفترض أي بشكل صحيح. حسنا-طرح المشكلة) المشكلة, مثل أن والثوابت هو fpt.تلك parameterizations استخدام اللغات والتي أفترض أن ما هو موضح هنا.مثل هذا "تافهة" (في ضوء السؤال ، وليس في ضوء صعوبة) تحديد المعايير والثوابت يهدف إلى تجاهلها.حتى في "الكلمات" منفصلة سحلية:غير تافهة مجموعة المعلمة(ق) هو(هي) المقصود.

Answer 1

عليك أن تكون حذرا بعض الشيء مع سؤالك هنا.علما أن NP-hard المشكلة هو قرار المشكلة ، في حين FPT خوارزميات حل parametrized قرار أو مشاكل البحث.لذا فإن السؤال هو قليلا سيئة تشكيلها.ومع ذلك, أعتقد أن السؤال ربما يقصد أن يسأل هو:

هل هناك NP-hard المشكلة التي يمكننا إضافة معلمة¹ لإنشاء "الطبيعية"² parametrised المشكلة التي لا FPT خوارزمية موجود ؟

والتي الجواب هو (دون قيد أو شرط!) نعم.

أولا وقبل كل شيء ، علما بأن FPT الفئة من المشاكل قابلة للحل عن طريق ثابت المعلمة لين العريكة الخوارزمية هي مجموعة فرعية من الصحيح XP, فئة "شريحة الحكيم متعدد الحدود" معلمات المشاكل التي يمكن حلها عن طريق متعدد الحدود-الوقت خوارزمية إذا كانت المعلمة هو ثابت.وبعبارة أخرى: $\mathrm{FPT} \subsetneq \mathrm{XP}$.(يجب أن أعترف أنني لست قادرا على تقديم دليل "معيار التخطيط القطري" الذي مصدري عروض المبرر الوحيد.ربما تعقيد المنظر يمكن أن تساعدني هنا)

المقبل, علما أنه منذ مشكلة واحدة على الأقل في XP لا يمكن حلها من قبل FPT-الخوارزمية ، أي XP-الثابت (بمعنى FPT-تخفيضات) المشكلة لا يمكن حلها من قبل FPT-خوارزمية.

في الفصل "يمكن اثباتها استعصاء:الطبقة XP" في داوني و الزملاء أساسيات معلمات تعقيد, إتمام الحجة التي تبين أن ما يسمونه حصاة اللعبة المشكلة هو XP-الثابت من قبل "إعادة تفسير" المشكلة التي هو معروف أن تكون على الأقل PSPACE الثابت (بعد "إزالة المعلمة") ، لذلك بالتأكيد NP-hard.انظر هناك كتاب الفصل للحصول على مزيد من التفاصيل.

---

اسمحوا لي أن أضيف أن هذه النتيجة كانت مفاجئة جدا بالنسبة لي كذلك ، لأن معظم العملية مشاكل, نحن بحاجة آل أنواع التخمين ($P eq NP$, ETH سيث 3-المبلغ ، الخ) ، ولكن هذه النتيجة هو الواقع الفعلي التي هي مستقلة عن أي التخمين.

---

_{1:توضيح من "إضافة معلمة" ، أعني إعطاء NP-hard المشكلة $L\subseteq \سيغما^*$, تعريف parametrized المشكلة $L'\subseteq \سيغما^* \تايمز \mathbb{N}$ كما $L':= \{\langle x, k angle \منتصف f(x)=ك\}$ لبعض وظيفة $f :\سيغما^* ightarrow \mathbb{N}$.هذا يلتقط بديهية فكرة أن معلمة إضافية تدابير خاصية الإدخال.
2:تعريف في 1 لا يزال يسمح بكل أنواع غريبة parameterizations مع وظائف مثل $f(x)\equiv 1$.من الناحية المثالية ، كنا بحاجة إلى $f$ لقياس شيء هام على سبيل المثال, ولكن يبدو من الصعب إضفاء الطابع الرسمي.لم أستطع التفكير في أي إضفاء الصفة الرسمية على أن يزيل كل "غير طبيعي" parameterizations أيضا.لذا بدلا من نسخ غير مفهوم "الطبيعية معلمات المشاكل" من داوني و الزملاء الكتاب.}

Answer 2

أود أن أقول نعم، ولكن عليك أن تقبل الشرط أن P $ \ NEQ $ np. تأخذ $ K $ -Coloring، حيث نريد تحديد ما إذا كان يمكن ملونة الرسم البياني مع $ k $ الألوان بحيث لا يكون لأي قمة متصلة بنفس اللون. بوضوح، يمكننا تقليل 3 تلوين إلى $ k $ -Coloring.

لنفترض

$ k $ -Coloring هو في FPT، ثم يوجد خوارزمية تحل هذه المشكلة في $ f ( K) \ CDOT N ^ {O (1)} $ . إذا حددنا $ k= 3 $ ، ثم نحصل على خوارزمية متعددة الحدود، وبالتالي يمكن حل 3 تلوين في وقت متعدد الحدود ما لم يكن P $ \ NEQ $ np. من الواضح، إذا P $ \ NEQ $ np، ثم لا توجد خوارزمية fpt for $ k $ -Coloring .

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

Answer 3

ربما خيار آخر ، أضعف بكثير من STanja هو الحل منفصلة السحالي الحل هو افتراض الهائل الوقت الفرضية (ETH).ETH يفترض $FPT eq W[1]$ (أو مجرد افتراض FPT $ eq$ W[1] مباشرة).

حتى مع FPT $ eq$ W[1] واحد لا تتحمل أي (غير تافهة) تحديد المعايير والثوابت $K-D$ من W[1]-من الصعب المشكلة FPT.مثال w[1] من الصعب المشكلة NP-hard* هو $k-زمرة$, لذا يوجد w[1]-من الصعب المشكلة التي هي NP-hard المشكلة.منذ (غير تافهة) تحديد المعايير والثوابت $K-D$ w[1]-من الصعب المشاكل ليست (في) fpt مع افتراض FPT $ eq$ W[1], وهذا يعني, أي (غير تافهة) تحديد المعايير والثوابت $K-D$ من NP-hard المشكلة $k-زمرة$ لا FPT.وهذا يعني أنه إذا كان FPT $ eq$ W[1] ، يوجد NP-hard المشكلة ليست FPT.

• قرار مشكلة ($k$)-زمرة هو NP-complete, ولذلك هو أيضا NP-hard كما في الصورة أدناه:

تنويه

لم تأتي مع هذه الحجة ، بل هو في الأساس تعليق منفصلة سحلية و هو تقريبا مثل الإجابة على السؤال:"لا $a$ موجود ؟ " مع:"أنا افترض أن $b$ موجود يا هناك يحدث أن تكون $a$ في مجموعة $b$, و منذ أن توليت $b$ موجود, ثم يجب أن يكون هناك أيضا موجودة وهي $a$, لذا نعم يوجد $a$.(كما يفسر أيضا منفصلة سحلية في التعليقات)