มีปัญหา NP-hard ที่ไม่มี Fixed-Parameter Tractable algorithm อยู่หรือไม่?

Question

คำถาม

มีปัญหา NP-hard หรือไม่ที่เราสามารถเพิ่มพารามิเตอร์¹เพื่อสร้างปัญหา parametrised "natural" ²ที่ไม่มีอัลกอริทึม FPT อยู่

1. จำเป็นต้องเพิ่มพารามิเตอร์เนื่องจากปัญหา NP-hard ปกติเป็นเพียงคำถามที่มีคำตอบใช่หรือไม่ใช่หากคุณต้องการ จำกัด พารามิเตอร์บางตัวคุณต้องระบุพารามิเตอร์ใด (แม้ว่าจะมีบางอย่างเช่น $k$- การลงสีอาจมีค่าที่ชัดเจนอยู่แล้ว) ดังนั้นการ "ระบุพารามิเตอร์ใด" จึงมีข้อ จำกัด ประการหนึ่งคือ "การเพิ่มพารามิเตอร์" ให้กับปัญหา คำอธิบายโดยละเอียดเพิ่มเติมรวมอยู่ในคำตอบของ Discrete Lizard
2. ฉันคิดว่า Natural พยายามที่จะยกเว้นการกำหนดพารามิเตอร์แบบ "เล็กน้อย" ขณะที่ฉันพูดถึงข้อสงสัยแรกในคำถามนี้ คำอธิบายโดยละเอียดอีกครั้งรวมอยู่ในคำตอบโดย Discrete Lizard

สงสัย

1. อาจเป็นคำถามเล็กน้อยเนื่องจากอาจเป็นไปได้ที่จะ "ยัดเยียด" ปัญหาทั้งหมดภายใน $f(k_1,k_2,..,k_m)$ ส่วนหนึ่งของ $f(k_1,k_2,..,k_m)n^c$ อัลกอริทึมในขณะที่ตั้งค่า $n=c'$ ที่ไหน $c'$เป็นค่าคงที่โดยพลการ แต่บางทีคำจำกัดความที่แน่นอนของ FPT จะป้องกันการใช้ (ab) แนวคิดของ FPT

จากความคิดเห็นของป๋อมนั้นมีวิธีเล็กน้อยในการกำหนดพารามิเตอร์ "ใด ๆ " (ฉันคิดว่าปัญหาใด ๆ ที่ได้รับการจัดวางอย่างเหมาะสม) เช่นการกำหนดพารามิเตอร์เป็น fpt parameterizations ผู้ใช้ภาษาซึ่งผมถือว่าเป็นสิ่งที่อธิบายที่นี่ การกำหนดพารามิเตอร์แบบ "เล็กน้อย" (ในแง่ของคำถามไม่ใช่ในแง่ของความยากลำบาก) การกำหนดพารามิเตอร์มีวัตถุประสงค์เพื่อละเว้น ดังนั้นใน "คำ" ของจิ้งจกแยก: ช่วงพารามิเตอร์ที่ไม่สำคัญคือ (มี) ไว้

Answer 1

คุณต้องระมัดระวังกับคำถามของคุณที่นี่ โปรดทราบว่าปัญหา NP-hard เป็นปัญหาในการตัดสินใจในขณะที่อัลกอริทึมของ FPT จะแก้ปัญหาการตัดสินใจหรือการค้นหาที่เป็นพารามิเตอร์ ดังนั้นคำถามจึงค่อนข้างไม่ดี อย่างไรก็ตามฉันคิดว่าคำถามที่คุณอาจตั้งใจจะถามคือ:

มีปัญหา NP-hard หรือไม่ที่เราสามารถเพิ่มพารามิเตอร์¹เพื่อสร้างปัญหา parametrised "natural" ²ที่ไม่มีอัลกอริทึม FPT อยู่

ซึ่งคำตอบคือ (โดยไม่มีเงื่อนไข!) ใช่

ก่อนอื่นโปรดทราบว่า FPT ซึ่งเป็นระดับของปัญหาที่แก้ไขได้โดยใช้อัลกอริธึมที่สามารถดึงพารามิเตอร์ได้คงที่เป็นชุดย่อยที่เหมาะสมของ XP ซึ่งเป็นคลาสของปัญหาที่กำหนดพารามิเตอร์แบบ "slice-wise polynomial" ที่สามารถแก้ไขได้โดยอัลกอริธึมเวลาแบบพหุนาม ถ้าพารามิเตอร์ได้รับการแก้ไข กล่าวอีกนัยหนึ่ง:$\mathrm{FPT} \subsetneq \mathrm{XP}$. (ฉันต้องสารภาพว่าฉันไม่สามารถให้การพิสูจน์โดย "เส้นทแยงมุมมาตรฐาน" ซึ่งแหล่งที่มาของฉันเสนอเป็นเหตุผลเดียวบางทีนักทฤษฎีความซับซ้อนอาจช่วยฉันได้ที่นี่)

ถัดไปโปรดทราบว่าเนื่องจากอย่างน้อยหนึ่งปัญหาใน XP ไม่สามารถแก้ไขได้ด้วยอัลกอริทึม FPT จึงไม่สามารถแก้ไขปัญหา XP-hard (ในแง่ของ FPT-reductions) ได้ด้วยอัลกอริทึม FPT

ในบท "Provable Intractability: The Class XP" ใน Downey and Fellows ' Fundamentals of Parameterized Complexityพวกเขาทำให้อาร์กิวเมนต์สมบูรณ์โดยแสดงให้เห็นว่าสิ่งที่พวกเขาเรียกว่าปัญหา PEBBLE GAMEนั้นยากสำหรับ XP โดยการ "ตีความซ้ำ" ปัญหาที่ทราบกันดีว่า อย่างน้อย PSPACE-hard (หลังจาก "ลบพารามิเตอร์") ดังนั้น NP-hard อย่างแน่นอน ดูบทหนังสือสำหรับรายละเอียดเพิ่มเติม

---

ฉันขอเพิ่มว่าผลลัพธ์นี้ทำให้ฉันประหลาดใจมากเช่นกันเพราะสำหรับปัญหาในทางปฏิบัติส่วนใหญ่เราต้องการการคาดเดาหลายประเภท ($P\neq NP$, ETH, SETH, 3-SUM ฯลฯ ) แต่ผลลัพธ์นี้เป็นความจริงที่ไม่ขึ้นกับการคาดเดาใด ๆ

---

_{1: เพื่อชี้แจงโดย "การเพิ่มพารามิเตอร์" ฉันหมายถึงปัญหา NP-hard $L\subseteq \Sigma^*$กำหนดปัญหาพาราเมตริก $L'\subseteq \Sigma^* \times \mathbb{N}$ เช่น $L':= \{\langle x, k\rangle \mid f(x)=k\}$ สำหรับบางฟังก์ชัน $f : \Sigma^* \rightarrow \mathbb{N}$. สิ่งนี้รวบรวมแนวคิดที่ใช้งานง่ายว่าพารามิเตอร์เพิ่มเติมจะวัดคุณสมบัติของอินพุต
2: คำจำกัดความใน 1 ยังคงอนุญาตการกำหนดพารามิเตอร์แปลก ๆ ทุกประเภทด้วยฟังก์ชันเช่น$f(x)\equiv 1$. ตามหลักการแล้วเราต้องการ$f$เพื่อวัดสิ่งที่มีความหมายเกี่ยวกับอินสแตนซ์ แต่ดูเหมือนจะยากที่จะทำให้เป็นทางการ ฉันไม่สามารถนึกถึงการทำให้เป็นทางการอื่นใดที่ลบการกำหนดพารามิเตอร์ที่ "ผิดธรรมชาติ" ทั้งหมดออกไปได้ ดังนั้นฉันจะคัดลอกแนวคิดที่ไม่เป็นทางการเกี่ยวกับ "ปัญหาที่กำหนดโดยธรรมชาติ" จากหนังสือของดาวนีย์และเฟลโลว์แทน}

Answer 2

ฉันจะตอบว่าใช่ แต่คุณต้องยอมรับเงื่อนไขว่า P $\neq$NP. ใช้$k$- การระบายสีซึ่งเราต้องการกำหนดว่ากราฟสามารถเป็นสีได้หรือไม่ $k$สีที่จุดยอดสองจุดที่เชื่อมต่อกันไม่มีสีเดียวกัน เห็นได้ชัดว่าเราสามารถลด 3-Coloring เป็น$k$- การระบายสี

สมมติ $k$- การระบายสีอยู่ใน FPT จากนั้นจึงมีอัลกอริทึมที่แก้ปัญหานี้ได้ $f(k) \cdot n^{O(1)}$. ถ้าเราตั้งค่า$k = 3$จากนั้นเราจะได้อัลกอริธึมเวลาพหุนามดังนั้น 3-Coloring จึงสามารถแก้ไขได้ในพหุนามเวลาเว้นแต่ P $\neq$NP. เห็นได้ชัดว่าถ้า P$\neq$ NP แล้วไม่มีอัลกอริทึม FPT สำหรับ $k$- การระบายสี

หากคุณกำลังมองหาบางสิ่งบางอย่างที่เข้มงวดยิ่งขึ้นในแง่ที่ว่ามันไม่มีอยู่จริงฉันไม่แน่ใจว่าจะพบปัญหาดังกล่าวหรือไม่

Answer 3

บางทีตัวเลือกอื่นที่อ่อนแอกว่าโซลูชันของ STanja และโซลูชันจิ้งจกแบบแยกส่วนอย่างมีนัยสำคัญคือการตั้งสมมติฐานเวลาเอกซ์โพเนนเชียล (ETH) ETH ถือว่า $FPT \neq W[1]$ (หรือสมมติว่าเป็น FPT $\neq$ W [1] โดยตรง)

ด้วย FPT $\neq$ W [1] หนึ่งถือว่าไม่มีการกำหนดพารามิเตอร์ (ไม่สำคัญ) $K-D$ของ W [1] - ปัญหายากคือ FPT ตัวอย่างของปัญหาที่ยากของ aw [1] ที่ NP-hard * คือ$k-clique$ดังนั้นจึงมีปัญหา aw [1] - ปัญหายากที่เป็นปัญหา NP-hard ตั้งแต่การกำหนดพารามิเตอร์ (ไม่สำคัญ)$K-D$ w [1] - ปัญหาที่ยากไม่ได้ (ใน) fpt ด้วยสมมติฐาน FPT $\neq$ W [1] หมายถึงการกำหนดพารามิเตอร์ใด ๆ (ที่ไม่สำคัญ) $K-D$ ของปัญหา NP-hard $k-Clique$ไม่ใช่ FPT นั่นหมายความว่าถ้า FPT$\neq$ W [1] มีปัญหา NP-hard ที่ไม่ใช่ FPT

• ปัญหาการตัดสินใจ ($k$) -clique เป็น NP-completeดังนั้นจึงเป็น NP-hard ตามภาพด้านล่างแสดง:

ข้อจำกัดความรับผิดชอบ

ฉันไม่ได้มาพร้อมกับข้อโต้แย้งนี้มันเป็นความคิดเห็นของจิ้งจกแบบไม่ต่อเนื่องและเกือบจะเหมือนกับการตอบคำถาม: "ไม่ $a$ มีอยู่จริง? "กับ:" ฉันคิดอย่างนั้น $b$ มีอยู่โอ้มี $a$ ที่อยู่ในชุด $b$และเนื่องจากฉันสันนิษฐาน $b$ มีอยู่แล้วก็ต้องมีไฟล์ $a$ใช่มีไฟล์ $a$. (ตามที่อธิบายโดยจิ้งจกแยกในความคิดเห็น)