ในวิทยาการคอมพิวเตอร์ความซับซ้อนแบบพารามิเตอร์ (parameterized complexity)เป็นสาขาหนึ่งของทฤษฎีความซับซ้อน ในการ คำนวณที่มุ่งเน้นการจำแนกปัญหาการคำนวณตามความยากโดยเนื้อแท้ของปัญหาโดยสัมพันธ์กับ พารามิเตอร์ หลายตัวของอินพุตหรือเอาต์พุต จากนั้นจึงวัดความซับซ้อนของปัญหาเป็นฟังก์ชันของพารามิเตอร์เหล่านั้น วิธีนี้ช่วยให้สามารถจำแนก ปัญหา NP-hardได้ในระดับที่ละเอียดกว่าในแบบดั้งเดิม ซึ่งความซับซ้อนของปัญหาจะวัดเป็นฟังก์ชันของจำนวนบิตในอินพุตเท่านั้น วิธีนี้ได้รับการสาธิตครั้งแรกในงานของGurevich, Stockmeyer & Vishkin (1984) และงานวิจัยเชิงระบบชิ้นแรกเกี่ยวกับความซับซ้อนแบบพารามิเตอร์นั้นดำเนินการโดยDowney & Fellows (1999 )

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

ภายใต้สมมติฐานที่ว่าP ≠ NPจะมีปัญหาทางธรรมชาติมากมายที่ต้องใช้เวลาประมวล ผลมากกว่าพหุนาม เมื่อวัดความซับซ้อนในแง่ของขนาดอินพุตเท่านั้น แต่สามารถคำนวณได้ในเวลาที่เป็นพหุนามเมื่อเทียบกับขนาดอินพุต และเป็นเลขชี้กำลังหรือแย่กว่านั้นเมื่อเทียบกับพารามิเตอร์kดังนั้น หากkถูกกำหนดไว้ที่ค่าเล็กๆ และการเติบโตของฟังก์ชันเมื่อเทียบกับkมีค่าค่อนข้างน้อย ปัญหาเหล่านี้ก็ยังสามารถพิจารณาได้ว่า "สามารถจัดการได้" แม้ว่าจะถูกจัดประเภทตามประเพณีว่าเป็น "ไม่สามารถจัดการได้" ก็ตาม

อัลกอริทึมดังกล่าวเรียกว่า อัลกอริทึมที่สามารถแก้ไข ได้ด้วยพารามิเตอร์คงที่ (Fixed-Parometer Tractableหรือ FPT) เนื่องจากสามารถแก้ปัญหาได้อย่างมีประสิทธิภาพ (เช่น ในเวลาพหุนาม) สำหรับค่าคงที่ของพารามิเตอร์ที่กำหนดไว้ ปัญหาที่มีพารามิเตอร์ซึ่งอนุญาตให้ใช้อัลกอริทึม FPT ดังกล่าวเรียกว่า ปัญหา ที่สามารถแก้ไขได้ด้วยพารามิเตอร์คงที่และอยู่ในกลุ่มFPTและชื่อเดิมของทฤษฎีความซับซ้อนที่มีพารามิเตอร์คือความสามารถในการแก้ไขด้วยพารามิเตอร์คงที่ (Fixed-Parometer Tractable )

โจทย์หลายข้อมีรูปแบบดังนี้: กำหนดให้วัตถุxและจำนวนเต็มที่ ไม่เป็นลบ k xมีคุณสมบัติบางอย่างที่ขึ้นอยู่กับkหรือไม่?

ตัวอย่างเช่น สำหรับปัญหาการปกคลุมจุดยอด (vertex cover problem ) พารามิเตอร์อาจเป็นจำนวนจุดยอดในการปกคลุมนั้น ส่วนปัญหาการปกคลุมจุดยอดขั้นต่ำ (minimal vertex cover problem) ถามว่า:

ในการใช้งานหลายๆ อย่าง เช่น ในการจำลองการแก้ไขข้อผิดพลาด เราสามารถสมมติให้พารามิเตอร์นั้น "เล็ก" เมื่อเทียบกับขนาดอินพุตทั้งหมด ดังนั้นจึงเป็นเรื่องยากที่จะหาอัลกอริทึมที่มีประสิทธิภาพแบบเลขชี้กำลังเฉพาะกับk เท่านั้น ไม่ใช่กับขนาดอินพุต

ด้วยวิธีนี้ ความซับซ้อนแบบพารามิเตอร์สามารถมองได้ว่าเป็น ทฤษฎีความซับซ้อน สองมิติแนวคิดนี้ได้รับการกำหนดเป็นทางการดังต่อไปนี้:

ปัญหาแบบ มีพารามิเตอร์ คือ ภาษาโดยที่คือตัวอักษรจำกัด ส่วนประกอบที่สองเรียกว่าพารามิเตอร์ของปัญหา${\displaystyle L\subseteq \Sigma ^{*}\times \mathbb {N} }$${\displaystyle \Sigma }$

ปัญหาที่มีพารามิเตอร์Lเรียก ว่า ปัญหา ที่สามารถแก้ไขได้ด้วยพารามิเตอร์คงที่ (Fixed-parameter tractable หรือ FPT ) หากคำถาม " ?" สามารถตัดสินได้ในเวลาการทำงานโดยที่fเป็นฟังก์ชันใดๆ ที่ขึ้นอยู่กับk เท่านั้น ระดับความซับซ้อนที่สอดคล้องกันเรียกว่า FPT (Fixed-parameter tractable )${\displaystyle (x,k)\in L}$${\displaystyle f(k)\cdot |x|^{O(1)}}$

ปัญหาที่มีพารามิเตอร์จะใช้พารามิเตอร์ตามธรรมชาติเมื่อพารามิเตอร์นั้นคือขนาดของคำตอบของปัญหา

ตัวอย่างเช่น มีอัลกอริทึมที่แก้ปัญหาการครอบคลุมจุดยอดในเวลา^{[ 1 ]}โดยที่nคือจำนวนจุดยอดและkคือขนาดของการครอบคลุมจุดยอด ซึ่งหมายความว่าการครอบคลุมจุดยอดสามารถจัดการได้ด้วยพารามิเตอร์คงที่โดยมีขนาดของคำตอบเป็นพารามิเตอร์ (พารามิเตอร์ตามธรรมชาติ) ${\displaystyle O(kn+1.274^{k})}$

FPT (Fixed Parameter Tractable) คือกลุ่มของปัญหาการตัดสินใจที่สามารถตัดสินได้ในเวลาที่แน่นอน โดยที่fเป็นฟังก์ชันที่คำนวณได้โดยทั่วไป ฟังก์ชันนี้มักถูกมองว่าเป็นฟังก์ชันเอกซ์โปเนนเชียลเดี่ยว เช่น แต่คำจำกัดความนี้ยอมรับฟังก์ชันที่เติบโตเร็วกว่านั้นด้วย ซึ่งเป็นสิ่งสำคัญ สำหรับ ประวัติศาสตร์ช่วงแรกของกลุ่มปัญหานี้ ส่วนสำคัญของคำจำกัดความคือการไม่รวมฟังก์ชันในรูปแบบเช่น${\displaystyle f(k)\cdot {|x|}^{O(1)}}$${\displaystyle 2^{O(k)}}$${\displaystyle f(n,k)}$${\displaystyle k^{n}}$

คลาสFPL (เชิงเส้นพารามิเตอร์คงที่) คือคลาสของปัญหาที่สามารถแก้ไขได้ในเวลาสำหรับฟังก์ชันที่คำนวณได้f บาง ฟังก์ชัน^{[ 2 ]}ดังนั้น FPL จึงเป็นคลาสย่อยของ FPT ตัวอย่างเช่น ปัญหา ความพึงพอใจของบูลีน ซึ่งมีพารามิเตอร์เป็นจำนวนตัวแปร สูตรที่กำหนดขนาดmที่มี ตัวแปร kสามารถตรวจสอบได้ด้วยวิธีบรูทฟอร์ซในเวลาการครอบคลุมจุดยอดขนาดk ในกราฟลำดับnสามารถหาได้ในเวลาดังนั้นปัญหาการครอบคลุมจุดยอดจึงอยู่ใน FPL ด้วย ${\displaystyle f(k)\cdot |x|}$${\displaystyle O(2^{k}m)}$${\displaystyle O(2^{k}n)}$

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

มีคำจำกัดความทางเลือกอื่นๆ ของ FPT อยู่หลายแบบ ตัวอย่างเช่น ข้อกำหนดด้านเวลาในการทำงานสามารถแทนที่ด้วยนอกจากนี้ ปัญหาที่มีพารามิเตอร์จะอยู่ใน FPT หากมีสิ่งที่เรียกว่าเคอร์เนลการสร้างเคอร์เนลเป็นเทคนิคการประมวลผลล่วงหน้าที่ลดอินสแตนซ์ดั้งเดิมให้เหลือ "เคอร์เนลแบบแข็ง" ซึ่งอาจมีขนาดเล็กกว่ามาก แต่เทียบเท่ากับอินสแตนซ์ดั้งเดิม และมีขนาดที่ถูกจำกัดโดยฟังก์ชันในพารามิเตอร์ ${\displaystyle f(k)+|x|^{O(1)}}$

FPT ปิดภายใต้แนวคิดการลดรูป ที่มีพารามิเตอร์ เรียกว่าการลดรูป fptเรากล่าวว่าปัญหาที่มีพารามิเตอร์หนึ่งลดรูป fpt เป็น ก็ต่อเมื่อมีฟังก์ชันสองฟังก์ชัน อยู่จริงโดยที่ ${\displaystyle L}$${\displaystyle L'}$${\displaystyle (x,k)\mapsto x',k\mapsto k'}$

• ${\displaystyle (x,k)\in L}$ก็ต่อเมื่อ${\displaystyle (x',k')\in L'}$
• ${\displaystyle (x,k)\mapsto x'}$สามารถแก้ไขได้ด้วยพารามิเตอร์คงที่
  • กล่าวคือ มีค่าคงที่และฟังก์ชัน อยู่ ซึ่งทำให้สามารถคำนวณได้ในเวลา${\displaystyle c}$${\displaystyle k\mapsto k''}$${\displaystyle (x,k)\mapsto x'}$${\displaystyle \leq k''|x|^{c}}$

เห็นได้ชัดว่า FPT ครอบคลุมปัญหาที่คำนวณได้ในเวลาพหุนามทั้งหมด นอกจากนี้ยังครอบคลุมปัญหาการหาค่าเหมาะสมที่สุดใน NP ที่อนุญาตให้ใช้แผนการประมาณค่าในเวลาพหุนามที่มีประสิทธิภาพ (EPTAS)ด้วย

XPคือกลุ่มของปัญหาที่มีพารามิเตอร์ ซึ่งสามารถแก้ไขได้ภายในเวลาที่กำหนดสำหรับ ฟังก์ชันคำนวณf บางฟังก์ชัน${\displaystyle n^{f(k)}}$

ปัญหาเหล่านี้เรียกว่าปัญหา พหุนาม แบบแบ่งส่วน (slicewise polynomial) ในแง่ที่ว่าแต่ละ "ส่วน" ของค่า k คงที่นั้น มีอัลกอริทึมแบบเวลาพหุนาม แม้ว่าเลขชี้กำลังอาจแตกต่างกันสำหรับแต่ละค่า kก็ตาม ลองเปรียบเทียบกับ FPT ซึ่งอนุญาตให้ใช้ค่าสัมประสิทธิ์นำหน้าคงที่ที่แตกต่างกันสำหรับแต่ละค่าของ k เท่านั้น

XP ประกอบด้วย FPT อย่างเคร่งครัดโดยใช้การหาค่าแนวทแยง

para-NPคือกลุ่มของปัญหาการตัดสินใจที่สามารถตัดสินได้ในเวลาที่ไม่แน่นอน สำหรับฟังก์ชันที่คำนวณ ได้ fบางฟังก์ชัน${\displaystyle f(k)\cdot |x|^{O(1)}}$

${\displaystyle {\textsf {FPT}}={\textsf {para-NP}}}$ก็ต่อเมื่อ^{[ 3 ]}${\displaystyle {\textsf {P}}={\textsf {NP}}}$

ปัญหาหนึ่งเรียกว่าปัญหาพารา-NP-ฮาร์ดหากปัญหานั้นเป็น ปัญหา NP- ฮาร์ดอยู่แล้วสำหรับค่าคงที่ของพารามิเตอร์ กล่าวคือ มี "ส่วนย่อย" ของค่า k ที่กำหนดไว้ ซึ่งเป็นปัญหา NP-ฮาร์ด ปัญหาที่มีพารามิเตอร์ซึ่งเป็นปัญหาNP-ฮาร์ดไม่สามารถอยู่ในคลาส NP-ฮาร์ดได้ เว้นแต่ว่า k ≠ NP-ฮาร์ด ตัวอย่างคลาสสิกของปัญหาที่มีพารามิเตอร์ซึ่งเป็นปัญหา NP-ฮาร์ดคือการระบายสีกราฟซึ่งมีพารามิเตอร์เป็นจำนวนสีk ซึ่งเป็นปัญหา NP-ฮาร์ดอยู่แล้วสำหรับ k ≠ NP-ฮาร์ด (ดูการระบายสีกราฟ#ความซับซ้อนในการคำนวณ ) ${\displaystyle {\textsf {NP}}}$${\displaystyle {\textsf {NP}}}$${\displaystyle {\textsf {para-NP}}}$${\displaystyle {\textsf {XP}}}$${\displaystyle {\textsf {P}}={\textsf {NP}}}$${\displaystyle {\textsf {para-NP}}}$${\displaystyle {\textsf {NP}}}$${\displaystyle k=3}$

ในทฤษฎีความซับซ้อนแบบพารามิเตอร์ มีลำดับชั้นของคลาสความซับซ้อนอยู่บ้าง แต่ละคลาสจะปิดภายใต้การลด fpt คลาสที่สำคัญที่สุดคือลำดับชั้นWและลำดับชั้นA ^{[ 4 ]}

โดยทั่วไป การกำหนดระดับความซับซ้อนมีสองวิธี คือ ตามทฤษฎีเครื่องจักรและตามหลักตรรกศาสตร์ ในทฤษฎีเครื่องจักร ระดับความซับซ้อนถูกกำหนดให้เป็นเซตของปัญหาการตัดสินใจที่สามารถแก้ไขได้โดยเครื่องจักรประเภทหนึ่ง ในตรรกศาสตร์ ระดับความซับซ้อนถูกกำหนดให้เป็นเซตของปัญหาการตัดสินใจที่สามารถกำหนดได้โดยสูตรตรรกศาสตร์ประเภทหนึ่ง

น้ำหนักแฮมมิง ( เรียก สั้น ๆ ว่า น้ำหนัก ) ของสตริงไบนารี คือจำนวนเลข 1 ที่ปรากฏในสตริงนั้น

วงจรบูลีนเป็นกราฟทิศทางแบบไม่มีวงจร โดยที่โหนดเป็นเกตอย่างใดอย่างหนึ่งต่อไปนี้: AND, OR, NOT เกตขนาดเล็กคือเกตที่มี fan-in 0, 1 หรือ 2 ส่วนเกตอื่นๆ คือเกตขนาดใหญ่weftคือจำนวนเกตขนาดใหญ่ที่มากที่สุดที่สามารถทำได้บนเส้นทางใดๆ จากอินพุตไปยังเอาต์พุตdepthคือจำนวนเกต (ขนาดเล็กหรือขนาดใหญ่) ที่มากที่สุดที่สามารถทำได้บนเส้นทางใดๆ จากอินพุตไปยังเอาต์พุต ตามนิยามแล้ว weft ≤ depth

วงจรบูลีนเป็นวงจรโมโนโทนก็ต่อเมื่อไม่มีการใช้เกต NOT วงจรบูลีนเป็นวงจรแอนติโมโนโทนก็ต่อเมื่อมีรูปแบบที่ และเป็นอินพุตทั้งหมด และเป็นวงจรโมโนโทน ${\displaystyle \phi (\neg x_{1},\dots ,\neg x_{n})}$${\displaystyle x_{1},\dots ,x_{n}}$${\displaystyle \phi }$

เมื่อได้รับสิ่งใดสิ่งหนึ่ง:

• ${\displaystyle {\mathcal {L}}}$ภาษาตรรกะลำดับที่หนึ่งที่มีชุดสัญลักษณ์ความสัมพันธ์จำกัด
• ${\displaystyle \Gamma }$ซึ่งเป็นชุดของสูตรตรรกะลำดับที่หนึ่งในภาษานั้น

เรากำหนดให้เป็น ปัญหา การตรวจสอบแบบจำลองที่มีพารามิเตอร์สำหรับทูเปิลนี้ โดยแต่ละอินสแตนซ์ของปัญหามีดังนี้: ${\displaystyle \operatorname {p-MC} (\Gamma )}$

• อินพุต: และแบบจำลองจำกัดสำหรับภาษา${\displaystyle \phi \in \Gamma }$${\displaystyle A}$${\displaystyle {\mathcal {L}}}$
• พารามิเตอร์:${\displaystyle |\phi |}$
• ผลลัพธ์: ไม่ว่าจะเป็น${\displaystyle A\models \phi }$

สูตรมีรูปแบบโดยที่ตัวบ่งปริมาณจะสลับกันระหว่างการมีอยู่และสำหรับทั้งหมด และสูตรภายในไม่มีตัวบ่งปริมาณ (นั่นคือ เขียนด้วยตัวแปร ตัวเชื่อมบูลีน และความสัมพันธ์เท่านั้น) ^{[ 5 ] [ 6 ]}${\displaystyle \Sigma _{t}}$${\displaystyle \exists x_{1,1:m_{1}}\forall x_{2,1:m_{2}}\dots Qx_{t,1:m_{t}}\psi (x)}$${\displaystyle \psi (x)}$

สูตรมีรูปแบบเป็นโดยมีเงื่อนไขเพิ่มเติมว่า ${\displaystyle \Sigma _{t,s}}$${\displaystyle \exists x_{1,1:m_{1}}\forall x_{2,1:m_{2}}\dots Qx_{t,1:m_{t}}\psi (x)}$${\displaystyle m_{2}\leq s,m_{3}\leq s,\dots ,m_{t}\leq s}$

ในทางทฤษฎีเครื่อง ปัญหาที่มีพารามิเตอร์จะอยู่ในคลาสW[w][d]หากมีการลดรูป fpt ของปัญหาดังต่อไปนี้:

• มีจำนวนเต็มคงที่อยู่จำนวนหนึ่งซึ่งทำให้${\displaystyle w,d}$
• แต่ละอินสแตนซ์ จะถูก แปลงในเวลา fpt เป็นวงจรบูลีนที่มี weft ไม่เกินwและ depth ไม่เกินd${\displaystyle (x,k)}$
• ${\displaystyle (x,k)\in L}$ก็ต่อเมื่อวงจรมีการกำหนดค่าน้ำหนักkที่ เหมาะสมเท่านั้น

ในที่นี้เราจะเห็นว่า "W" ย่อมาจาก "น้ำหนัก" โปรดสังเกตว่าในคำจำกัดความข้างต้น ค่าต่างๆ นั้นเป็นอิสระจากแต่ตัววงจรเองขึ้นอยู่กับและอาจเปลี่ยนแปลงได้หากมีการเปลี่ยนแปลงค่าใดค่าหนึ่งระหว่าง หรือ${\displaystyle w,d}$${\displaystyle (x,k)}$${\displaystyle (x,k)}$${\displaystyle x}$${\displaystyle k}$

จากนั้น คลาสW[w]จะถูกกำหนดให้เป็นผลรวมของพวกมัน กล่าวโดยสรุปW[w]คือเซตของปัญหาที่สามารถลดรูป fpt ได้เป็นตระกูลของวงจรบูลีนเฉพาะอินสแตนซ์ที่มี weft และ depth ที่ถูกจำกัดด้วยค่าคงที่เฉพาะปัญหาบางค่า $${\displaystyle W[w][1]\subset W[w][2]\subset \dots \subset W[w]:=\bigcup _{d\geq 1}W[w][d]}$$${\displaystyle \leq w}$

วงจรปกติของ weft wและ depth dคือวงจรที่ชั้นแรกๆ ประกอบด้วยเกตขนาดเล็กเท่านั้น และชั้นสุดท้ายประกอบด้วยเกตขนาดใหญ่สลับกันของ AND และ OR เราสามารถทำซ้ำกฎการเชื่อมโยงและกฎการกระจายของเดอ มอร์แกนเพื่อทำให้วงจรเป็นปกติในเวลา fpt ได้ ดังนั้นโดยไม่เสียความเป็นทั่วไป เราสามารถพิจารณาเฉพาะวงจรปกติเท่านั้น^{[ 7 ]}${\displaystyle dw}$${\displaystyle w}$

ตามทฤษฎีแบบจำลอง คลาสW[t]ถูกกำหนดให้เป็นคลาสของปัญหาที่สามารถลดรูป fpt ได้เป็น ${\displaystyle \operatorname {p-MC} (\Sigma _{t,1})}$

ในขณะที่ ลำดับชั้น Wเป็นลำดับชั้นที่อยู่ใน NP ลำดับชั้น A เลียน แบบลำดับชั้นเวลาพหุนาม จากความซับซ้อนแบบคลาสสิกได้ อย่างใกล้ชิดยิ่งขึ้นในทางทฤษฎีเครื่องจักร ลำดับชั้น A ของปัญหาถูกกำหนดให้เป็นปัญหาที่สามารถลดรูป fpt ไปสู่การคำนวณโดยเครื่องจักรทัวริงแบบสลับ บางประเภท "A" ย่อมาจาก "สลับ" ^{[ 6 ]}

ตามทฤษฎีแบบจำลอง คลาสA[t]ถูกกำหนดให้เป็นคลาสของปัญหาที่สามารถลดรูป fpt ได้เป็น ${\displaystyle \operatorname {p-MC} (\Sigma _{t})}$

ตัวอย่างเช่น ปัญหา k -clique สามารถระบุได้ว่าเป็นปัญหาการตรวจสอบแบบจำลอง ภาษาดังกล่าวมีความสัมพันธ์ทวิภาคเดียวโดยที่หมายถึง " แบ่งปันขอบ" จากนั้น แบบจำลองจำกัดคือ กราฟ และจะมีk -clique ก็ต่อเมื่อ โดยที่สิ่งนี้แสดงให้เห็นว่า ปัญหา k -clique อยู่ใน ${\displaystyle E}$${\displaystyle E(x,y)}$${\displaystyle x,y}$${\displaystyle A}$${\displaystyle A\models \phi _{k}}$$${\displaystyle \phi _{k}:=\exists x_{1:k},\bigwedge _{1\leq i<j\leq n}E(x_{i},x_{j})}$$${\displaystyle A[1]}$

ปัญหาจะเรียกว่าA[i] -สมบูรณ์ก็ต่อเมื่อเป็นA[i]และ ปัญหา A[i] ใดๆ ก็ สามารถลดรูป fpt ไปสู่ปัญหานี้ได้

ตามนิยามแล้ว: $${\displaystyle W[0]\subset W[1]\subset \cdots ,\quad W[i]\subset A[i],\quad A[0]\subset A[1]\subset \cdots }$$${\displaystyle {\mathsf {FPT}}=W[0]=A[0]}$

• ${\displaystyle W[0]=A[0]}$เนื่องจากไม่มีตัวบ่งปริมาณเลย ดังนั้นจึงไม่มีความแตกต่างระหว่างและ${\displaystyle \Sigma _{0}}$${\displaystyle \Sigma _{0}}$${\displaystyle \Sigma _{0,1}}$
• ${\displaystyle {\mathsf {FPT}}\subset W[0]}$สำหรับปัญหา FPT ใดๆก็สามารถลดรูปให้เหลือ FPT ได้อย่างง่ายดายดังนี้: แก้ปัญหาในเวลา FPT จากนั้นส่งออกวงจร Yes/No ที่เรียบง่ายซึ่งไม่ทำอะไรเลยนอกจากส่งออกค่าบูลีนที่ถูกต้อง${\displaystyle L}$${\displaystyle (x,k)\in L}$
• ${\displaystyle {\mathsf {FPT}}\supset W[0]}$สำหรับปัญหา W[0] ใดๆและอินสแตนซ์ปัญหาใดๆวงจรจะมี weft และdepth เป็น 0 โดยที่ถูกกำหนดไว้แล้ว ดังนั้นเอาต์พุตจะถูกกำหนดโดยอินพุตไม่เกิน อินพุตอื่นๆ ทั้งหมดสามารถใช้งานได้อย่างอิสระ ดังนั้นจึงต้องคำนวณอินพุตที่เป็นไปได้ทั้งหมดแบบ brute-force หากอินพุตใดมีน้ำหนัก k' และทำให้เอาต์พุตของวงจรเป็น True ให้ตรวจสอบว่ายังมีอินพุตเหลือเพียงพอที่จะเติมน้ำหนักหรือไม่${\displaystyle L}$${\displaystyle c\in L}$${\displaystyle c}$${\displaystyle \leq d}$${\displaystyle d}$${\displaystyle 2^{d}}$${\displaystyle 2^{2^{d}}}$${\displaystyle \#({\text{อินพุตของ }}c)-2^{d}\geq kk'}$

${\displaystyle W[1]=A[1]}$[ ^{6 ]​}

โดยสัญชาตญาณ ปัญหาในคลาส W[1] สามารถตีความได้ในรูปแบบ: มีวัตถุขนาดkที่มีคุณสมบัติที่ตรวจสอบได้ในระดับท้องถิ่นหรือไม่? ในสูตร จะอยู่ในรูปแบบในความเป็นจริงW[1]ยุบตัวลงเป็นW[1, 2]ซึ่งเป็นคลาสของปัญหาที่ลดรูป fpt ได้เป็นวงจรบูลีนในรูปแบบนั่นคือ AND ขนาดใหญ่เหนือ OR จำนวนมากที่มี fan-in 2 ^{[ 8 ]}$${\displaystyle \bigvee _{u_{1},\dots ,u_{k}}({\text{วัตถุที่สร้างขึ้นตาม }}u_{1},\dots ,u_{k}{\text{ มีคุณสมบัติเฉพาะที่}})}$$${\displaystyle \bigwedge _{i}(x_{i,1}\lor x_{i,2})}$

ตัวอย่างของ ปัญหา W[1]ที่สมบูรณ์ ได้แก่: ^{[ 8 ]}

• ชุดอิสระ
  • อินพุต: กราฟG
  • พารามิเตอร์: จำนวนเต็มk
  • ผลลัพธ์: ตรวจสอบว่าGประกอบด้วยเซตอิสระขนาดk หรือไม่
• กลุ่ม
  • อินพุต: กราฟG
  • พารามิเตอร์: จำนวนเต็มk
  • ผลลัพธ์: ตรวจสอบว่ากราฟ Gมีคลิกขนาดk หรือไม่
• ตัวบล็อกแบบไบพาร์ไทต์
  • อินพุต: กราฟสองส่วน${\displaystyle (V_{1},V_{2},E)}$
  • พารามิเตอร์: จำนวนเต็มk
  • ผลลัพธ์: ตรวจสอบว่ามีเซตย่อยที่มีขนาดk อยู่ หรือไม่ โดยที่สมาชิกใดๆ ก็ตามจะมีสมาชิกข้างเคียงกล่าวอีกนัยหนึ่งคือไม่ปิดกั้นสมาชิก อื่น${\displaystyle S\subset V_{1}}$${\displaystyle v\in V_{2}}$${\displaystyle u\not \in S}$${\displaystyle S}$${\displaystyle V_{2}}$
• น้ำหนัก- k 2-ความพึงพอใจ
  • อินพุต: สูตร เชื่อมประโยคปกติในรูปแบบโดยที่iครอบคลุมอนุประโยคต่างๆ${\displaystyle \bigwedge _{i}(p_{i,1}\lor p_{i,2})}$
  • พารามิเตอร์: จำนวนเต็มk
  • ผลลัพธ์: มีค่าน้ำหนัก k ที่ตรงตามข้อกำหนดของสูตรหรือไม่
• ปัญหาเครื่องจักรทัวริงแบบสั้น
  • อินพุต: เครื่องจักรทัวริง แบบ ไม่กำหนด M , สตริงx , จำนวนเต็มk
  • ผลลัพธ์: ตรวจสอบว่ามีเส้นทางการคำนวณหนึ่งเส้นทางหรือไม่ ที่ทำให้Mยอมรับx ได้ ภายในไม่เกินkขั้นตอน

โปรดทราบว่าปัญหาที่ไม่ปิดกั้นธรรมดาคือ FPT ^{[ 9 ]}

หมายเหตุเกี่ยวกับเครื่องจักรทัวริงแบบไม่กำหนด เครื่องจักรอาจถูกกำหนดโดยสูตรมาตรฐานใด ๆ ก็ได้ โดยปกติแล้วเราจะพิจารณาเครื่องจักรทัวริงแบบเทปเดียว แต่ปัญหาเครื่องจักรทัวริงแบบสั้นยังคงเป็นW[1]แม้ว่าเราจะอนุญาตให้มี เทป f ( k ) และแม้แต่ เทป f(k) มิติ f ( k )ก็ตามแต่แม้จะมีการขยายนี้ ข้อจำกัดเกี่ยวกับ ขนาดตัวอักษรเทป f ( k ) ก็ยังคงเป็นปัญหา FPT ที่สำคัญ เนื่องจากเครื่องจักรMเองเป็นส่วนหนึ่งของอินพุตของปัญหา ขนาดอินพุตnจึงใหญ่กว่าจำนวนสถานะของMด้วยวิธีนี้ เครื่องจักรทัวริงสามารถเลือกเส้นทางการคำนวณที่เป็นไปได้หนึ่งเส้นทางต่อขั้นตอน โดยเข้าถึงขั้นตอนทั้งหมดภายในเวลาkดังนั้นเราจึงเห็นว่าW[1]ไม่ได้อยู่ในขอบเขตของFPT อย่าง ชัดเจน${\displaystyle n}$${\displaystyle n^{O(k)}}$

ปัญหาเซตอิสระสามารถเข้ารหัสได้ดังนี้ เมื่อกำหนดกราฟแต่ละกราฟปัญหาเซตอิสระของกราฟนั้นจะถูกเข้ารหัสด้วยวงจรบูลีน weft-1 ต่อไปนี้: โดยที่คือเซตของขอบในกราฟ กราฟจะมีเซตอิสระขนาดkก็ต่อเมื่อมีอินพุตน้ำหนักkไปยังวงจรบูลีนของกราฟนั้น ซึ่งทำให้ได้ผลลัพธ์เป็น 1 ${\displaystyle (V,E)}$$${\displaystyle \Phi _{\text{IS}}(V,E):=\bigwedge _{\{u,v\}\in E}(\neg x_{u}\lor \neg x_{v})}$$${\displaystyle E}$

ปัญหาคลิกสามารถเขียนโค้ดได้ดังนี้ตรวจสอบว่าคู่จุดยอดใดๆ ที่ไม่ได้สร้างขอบจะไม่สามารถถูกเลือกได้ ดังนั้นเซตของจุดยอดใดๆ ที่ถูกเลือกจึงถูกบังคับให้เป็นกลุ่มคลิก $${\displaystyle \Phi _{\text{clique}}(V,E):=\bigwedge _{\{u,v\}\subset V,u\neq v,\{u,v\}\not \in E}(\neg x_{u}\lor \neg x_{v})}$$

ปัญหาเครื่องจักรทัวริงแบบสั้นสามารถแปลงเป็นสูตรบูลีนได้โดยใช้แนวคิดการพิสูจน์แบบเดียวกับทฤษฎีบท Cook–Levinซึ่งแสดงให้เห็นว่า SAT เป็นปัญหา NP-complete โดยการเข้ารหัสร่องรอยการคำนวณของเครื่องจักรทัวริงเป็นสูตรบูลีน การพิสูจน์ต่อไปนี้มาจาก^{[ 8 ] [ 10 ]}โดยเฉพาะอย่างยิ่ง กำหนดตัวแปรเชิงประพจน์:

• ${\displaystyle s_{t,i,j,a,b}}$: ณ เวลาtเครื่องจักรทัวริงอยู่ในสถานะiและเปลี่ยนไปสู่สถานะjโดยอ่านค่าaและเขียนค่าb
• ${\displaystyle y_{t,p,a,b}}$: ณ เวลาtตำแหน่งเทปpมีสัญลักษณ์aและ ณ เวลา(t+1)มีสัญลักษณ์b

ในบรรดาดัชนีต่างๆ เวลาtและตำแหน่งเทปpมีช่วงตั้งแต่1:kช่วงของดัชนีไปยังสถานะi, jการเปลี่ยนสถานะmและสัญลักษณ์a, b ของเครื่องทัวริง ถูกกำหนดโดยคำอธิบายของเครื่อง M แต่ทั้งสองอย่างมีขอบเขตภายใน1: n

จากนั้น สูตรดังกล่าวเป็นการเชื่อมโยงของข้อความต่างๆ ที่บังคับใช้ข้อจำกัดดังต่อไปนี้: ${\displaystyle \Phi _{{\text{STM}},k}(M,x)}$

• การเปลี่ยนสถานะของเครื่องจักรทัวริงทุกสถานะไม่ได้ถูกห้ามโดยกฎการเปลี่ยนสถานะแบบไม่แน่นอนเสมอไป กล่าวอีกนัยหนึ่งคือมีข้อความลักษณะนี้ อยู่${\displaystyle s_{t,i,j,a,b}\to \neg s_{t+1,i',j',a',b'}}$${\displaystyle \neg s_{t,i,j,a,b}\lor \neg s_{t+1,i',j',a',b'}}$${\displaystyle O(kn^{4})}$
• เครื่องจักรทัวริงไม่สามารถอยู่ในสองตำแหน่งพร้อมกันได้ และไม่สามารถเปลี่ยนสถานะสองครั้งพร้อมกันได้
• การเปลี่ยนสถานะของเซลล์เทปทุกครั้งไม่ได้ถูกห้ามโดยกฎการเปลี่ยนสถานะแบบไม่แน่นอน
• แต่ละสถานะของเซลล์เทปไม่สามารถมีสัญลักษณ์สองตัวพร้อมกันได้
• ณ เวลา 0 เครื่องจักรทัวริงยังคงอยู่ในสถานะและตำแหน่งเริ่มต้น และค่า xยังไม่ได้ถูกลบออกจากเทป
• เครื่องจักรทัวริงไม่ได้อยู่ในสถานะที่ไม่ยอมรับ ณเวลาk

จากนั้น การติดตามการคำนวณผ่านเครื่องจักรทัวริงจะถูกกำหนดอย่างสมบูรณ์โดยการตั้งค่าตัวแปรk ให้ เป็น True เพื่อระบุการเปลี่ยนสถานะของเครื่องจักรทัวริงในแต่ละช่วงเวลา และการตั้งค่าตัวแปรให้เป็น True เพื่อระบุการเปลี่ยนสถานะของเทปในแต่ละช่วงเวลา ซึ่งจะลดปัญหาเครื่องจักรทัวริงแบบสั้นให้เหลือเพียงปัญหาการหาการกำหนดค่าที่สอดคล้องกับน้ำหนักให้กับวงจรบูลีนแบบแอนติโมโนโทนที่มีเส้นด้ายพุ่ง 1 เส้นและความลึก 2 เส้น ${\displaystyle s_{t,i,j,a,b}}$${\displaystyle k^{2}}$${\displaystyle y_{t,p,a,b}}$${\displaystyle (k+k^{2})}$

ปัญหา W[2]ตามสัญชาตญาณมีรูปแบบดังนี้: เดาวัตถุที่มีขนาดkดำเนินการประมวลผลเฉพาะที่กับวัตถุ จากนั้นดำเนินการประมวลผลทั่วโลกหนึ่งครั้ง

ตัวอย่างของ ปัญหา W [2]-สมบูรณ์ ได้แก่

• การตัดสินว่ากราฟที่กำหนดนั้นมีเซตครอบงำที่มีขนาดk หรือไม่
• การตัดสินใจว่า เครื่องทัวริงแบบหลายเทปที่ไม่กำหนดจะยอมรับภายในkขั้นตอนหรือไม่ ("ปัญหาการยอมรับเครื่องทัวริงแบบหลายเทปสั้น") ที่สำคัญคือ อนุญาตให้การแตกแขนงขึ้นอยู่กับn (เช่นเดียวกับตัวแปร W[1]) เช่นเดียวกับจำนวนเทป สูตรW [2]-complete ทางเลือกอื่นอนุญาตให้ ใช้เฉพาะเครื่องทัวริงแบบเทปเดียวเท่านั้น แต่ขนาดของตัวอักษรอาจขึ้นอยู่กับn

ปัญหาเซตครอบงำมีสูตรดังนี้ ${\displaystyle \Psi _{\text{dom}}(V,E)=\bigwedge _{u\in V}\bigvee _{v\in \operatorname {Neighbor} [u]}x_{v}}$

ปัญหาบางอย่างเป็นที่ทราบกันว่าเป็นW[i] -สมบูรณ์ แม้ว่าจะอยู่ในรูปแบบทั่วไปในการคำนวณ และมักจะศึกษาภายในทฤษฎีความซับซ้อนแบบพารามิเตอร์เองก็ตาม จากประสบการณ์ในปี 2013 ปัญหาพารามิเตอร์ที่เกิดขึ้นตามธรรมชาติเกือบทั้งหมดที่พวกเขาศึกษา พบว่าเป็นW[0] -สมบูรณ์, W[1] -สมบูรณ์ หรือW[2] -สมบูรณ์ โดยทั่วไปจะใช้ดังต่อไปนี้: ^{[ 4 ]}

• ความพึงพอใจ แบบถ่วงน้ำหนักi -ปกติ: ^{[ 7 ] [ 4 ] : ทฤษฎีบท 23.2.1} เมื่อกำหนดสูตรบูลีนที่เขียนเป็น AND ของ OR ของ AND ของ ... ของตัวแปรที่อาจถูกปฏิเสธ โดยมีชั้นของ AND หรือ OR สลับกัน สามารถทำให้เป็นจริงได้โดยการตั้ง ค่าตัวแปร k ตัว ให้เป็น 1 หรือไม่? ${\displaystyle i+1}$
  • โครงร่างการพิสูจน์: วงจร W[i] ใดๆ สามารถทำให้เป็นมาตรฐานได้ในเวลา fpt โดยการทำซ้ำกฎการเชื่อมโยงและกฎการกระจายของเดอ มอร์แกน ซึ่งแสดงให้เห็นว่าปัญหานี้คือW[i]สมบูรณ์
• ถ้าi>0เป็นจำนวนคู่แล้ว
  • ${\displaystyle {\text{monotone-}}W[i]=W[i]}$.
  • ความสามารถในการทำให้เป็นมาตรฐาน แบบถ่วงน้ำหนักโมโนโทนiคือW[i] -สมบูรณ์
  • โมโนโทนแบบถ่วงน้ำหนัก(i+1) -ความพึงพอใจปกติอยู่ในW[i ]
• ถ้าi>0เป็นจำนวนคี่ แล้ว
  • ${\displaystyle {\text{antimonotone-}}W[i]=W[i]}$
  • ความพึงพอใจ แบบถ่วงน้ำหนัก Antionotone i -Normalized คือW[i] -สมบูรณ์
  • ถ้าเช่นนั้น Weighted Antimonotone (i+1) -Normalized Satisfiability จะอยู่ในW[i ]${\displaystyle i\geq 3}$

ปัญหาเหล่านี้เป็นปัญหา "เทียม" โดยพื้นฐานแล้ว เนื่องจากไม่ได้มีการศึกษาเว้นแต่ในบริบทของความซับซ้อนแบบพารามิเตอร์ วรรณกรรมรายงานว่ามีปัญหาที่เกิดขึ้นตามธรรมชาติเพียงไม่กี่ปัญหาที่เป็นW[i] -สมบูรณ์สำหรับ: ${\displaystyle i\geq 3}$

• การตรวจจับการพึ่งพาการรวมในฐานข้อมูลเชิงสัมพันธ์นั้นสมบูรณ์W[3]
• ปัญหาบางประการในแบบจำลองห่วงโซ่อุปทานคือW[3] -สมบูรณ์หรือW[4] -สมบูรณ์^{[ 11 ]}

W[SAT]คือคลาสของปัญหาที่สามารถลดรูป fpt ให้เป็นปัญหา SAT ที่มีน้ำหนักได้: ^{[ 12 ]}

• อินพุต: สูตรบูลีน
• พารามิเตอร์: k
• ผลลัพธ์: ตรวจสอบว่าสูตรดังกล่าวมีค่าน้ำหนักkที่ตรงตามข้อกำหนด หรือไม่

ประกอบด้วยW[t]ทั้งหมด

W[P]คือคลาสของปัญหาที่สามารถลดรูป fpt ได้เป็นปัญหาของวงจรบูลีนแบบถ่วงน้ำหนัก: ^{[ 12 ]}

• อินพุต: วงจรบูลีน
• พารามิเตอร์: k
• เอาต์พุต: มีค่าน้ำหนักk ใดบ้าง ที่ทำให้วงจรส่งออกค่า True

ประกอบด้วยW[SAT]เนื่องจากสูตรบูลีนสามารถแปลงเป็นวงจรบูลีนได้อย่างมีประสิทธิภาพ โปรดทราบว่าโดยทั่วไปแล้วสิ่งที่ตรงกันข้ามจะไม่เป็นจริง เนื่องจากสูตรบูลีนที่เทียบเท่ากับวงจรบูลีนอาจมีขนาดใหญ่กว่าวงจรในเชิงเลขชี้กำลังอย่างหลีกเลี่ยงไม่ได้

ในทำนองเดียวกัน มันคือคลาสของปัญหาที่สามารถตัดสินได้โดยเครื่องทัวริงแบบไม่กำหนดเวลาซึ่งทำการเลือกแบบไม่กำหนดอย่างมากที่สุดในการคำนวณบน( เครื่องทัวริงแบบจำกัด k ) ^{[ 13 ] [ 4 ]}${\displaystyle h(k)\cdot {|x|}^{O(1)}}$${\displaystyle O(f(k)\cdot \log n)}$${\displaystyle (x,k)}$

เป็นที่ทราบกันว่า FPT อยู่ใน W[P] และเชื่อว่าการรวมนั้นเป็นไปอย่างเข้มงวด อย่างไรก็ตาม การแก้ไขปัญหานี้จะหมายถึงการแก้ปัญหา P เทียบกับ NP ด้วย

ความเชื่อมโยงอื่นๆ กับความซับซ้อนในการคำนวณที่ไม่มีพารามิเตอร์คือ FPT จะเท่ากับW [ P ] ก็ต่อเมื่อความสามารถในการทำให้วงจรเป็นจริงสามารถตัดสินได้ในเวลาหรือก็ต่อเมื่อมีฟังก์ชัน f ที่คำนวณได้ ไม่ลดลง และไม่จำกัดขอบเขต ซึ่งภาษาทั้งหมดที่รู้จักโดยเครื่องทัวริงแบบไม่กำหนดเวลาพหุนามโดยใช้ตัว เลือกแบบ ไม่กำหนดอยู่ใน  P${\displaystyle \exp(o(n))m^{O(1)}}$${\displaystyle f(n)\log n}$

W [ P ] อาจมองอย่างคร่าวๆ ได้ว่าเป็นกลุ่มของปัญหาที่เรามีเซตSที่ประกอบด้วย รายการ nรายการ และเราต้องการหาสับเซตที่มีขนาดkซึ่งมีคุณสมบัติบางอย่างเป็นจริง เราสามารถเข้ารหัสตัวเลือกเป็นรายการของ จำนวนเต็ม kตัวที่จัดเก็บในรูปแบบไบนารี เนื่องจากค่าสูงสุดที่เป็นไปได้ของจำนวนใดๆ เหล่านี้คือnจึงต้องใช้บิตสำหรับแต่ละจำนวน ดังนั้นจึงต้องใช้บิตทั้งหมดเพื่อเข้ารหัสตัวเลือก ดังนั้นเราจึงสามารถเลือกสับเซตด้วยตัวเลือกที่ไม่แน่นอนได้ ${\displaystyle T\subset S}$${\displaystyle \lceil \log _{2}n\rceil }$${\displaystyle k\cdot \lceil \log _{2}n\rceil }$${\displaystyle T\subset S}$${\displaystyle O(k\cdot \log n)}$

ลำดับ ชั้น W*คล้ายกับ ลำดับชั้น Wแต่กำหนดพารามิเตอร์ความลึกแทนที่จะคงค่าไว้คงที่ คลาส W*[t]ถูกกำหนดให้เป็นคลาสของปัญหาที่สามารถลดรูป fpt ให้เป็นปัญหานี้ได้: ^{[ 5 ]}

• อินพุต: วงจรบูลีนที่มีความกว้างของเส้นด้ายพุ่งไม่เกินt และความลึกไม่เกินk
• พารามิเตอร์: k
• เอาต์พุต: วงจรบูลีนมีน้ำหนักkที่ตรงตามเงื่อนไข หรือไม่

เกี่ยวข้องกับWโดย: ^{[ 4 ]}ลำดับ ชั้น AWได้รับมาจากการเพิ่มการสลับไปยังลำดับชั้นW คลาส AW[t]ถูกกำหนดให้เป็นคลาสของปัญหาที่สามารถลดรูป fpt ให้เป็นปัญหานี้ได้: ^{[ 5 ] [ 6 ]}$${\displaystyle W^{*}[1]=W[1],\;W^{*}[2]=W[2],\;W[t]\subset W^{*}[t]\subset W[t+2],\quad \forall t\geq 1}$$

• อินพุต: วงจรบูลีนที่มีค่า weft ไม่เกินtและการแบ่งอินพุตของวงจรเป็น${\displaystyle I_{1}\cup I_{2}\cup \cdots \cup I_{r}}$
• พารามิเตอร์:${\displaystyle (r,k_{1},\dots ,k_{r})}$
• เอาต์พุต: วงจรบูลีนสามารถเป็นจริงได้หรือไม่ภายใต้เงื่อนไข น้ำหนักสลับกัน${\displaystyle (k_{1},\dots ,k_{r})}$

การถ่วงน้ำหนักแบบสลับกันนั้นกำหนดไว้ดังนี้: ${\displaystyle (k_{1},\dots ,k_{r})}$

• มีเซตย่อยที่มีขนาดเท่ากับ n อยู่เซตหนึ่ง ซึ่งถ้าเรากำหนดค่าอินพุตเหล่านั้นเป็น True และค่าอินพุตอื่นๆ เป็น False แล้ว จะได้ว่า${\displaystyle J_{1}\subset I_{1}}$${\displaystyle k_{1}}$
• สำหรับเซตย่อยใดๆที่มีขนาดโดยที่ถ้าเราตั้งค่าอินพุตเหล่านั้นเป็น True และอินพุตอื่นๆ เป็น False แล้ว${\displaystyle J_{2}\subset I_{2}}$${\displaystyle k_{2}}$
• ...
• วงจรบูลีนให้ผลลัพธ์เป็น True

อาจตีความได้ว่าเป็นเกมสองผู้เล่น โดยผู้เล่นคนแรกพยายามทำให้วงจรส่งค่าออกมาเป็น True และผู้เล่นคนที่สองพยายามทำให้วงจรส่งค่าออกมาเป็น False ผู้เล่นคนแรกจะทำการเคลื่อนไหวโดยตั้งค่าอินพุตบางตัวให้เป็น True และบางตัวให้เป็น False จากนั้นผู้เล่นคนที่สองจะทำการเคลื่อนไหวกับอินพุตอื่นๆ ต่อไป เรื่อย ๆ วงจรจะอยู่ภายใต้เงื่อนไขน้ำหนักสลับกันก็ต่อเมื่อผู้เล่นคนแรกมีกลยุทธ์ที่ชนะเท่านั้น ${\displaystyle k_{1}}$${\displaystyle I_{1}}$${\displaystyle I_{2}}$${\displaystyle (k_{1},\dots ,k_{r})}$

ปรากฏว่าลำดับชั้นนั้นพังทลายลง: ดังนั้น ในเอกสารจึงใช้สัญลักษณ์ทั่วไปแทนพวกมัน: ${\displaystyle AW[1]=AW[2]=\cdots }$${\displaystyle AW[\ast ]:=AW[1]=AW[2]=\cdots }$

• อัลกอริทึมการประมาณค่าแบบพารามิเตอร์สำหรับปัญหาการหาค่าเหมาะสมที่สุดอัลกอริทึมที่ทำงานในเวลา FPT อาจประมาณค่าคำตอบได้

• วิกิเกี่ยวกับความซับซ้อนแบบพารามิเตอร์
• คู่มือรวมปัญหาที่มีพารามิเตอร์
• https://complexityzoo.net/Complexity_Zoo:W