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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ตามทฤษฎีแบบจำลอง คลาส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 สามารถระบุได้ว่าเป็นปัญหาการตรวจสอบแบบจำลอง ภาษาดังกล่าวมีความสัมพันธ์ทวิภาคเพียงหนึ่งเดียว${\displaystyle E}$, ที่ไหน${\displaystyle E(x,y)}$วิธี "${\displaystyle x,y}$แบ่งปันขอบ" จากนั้น โมเดลจำกัด${\displaystyle A}$เป็นกราฟ และจะมีk-คลิกก็ต่อเมื่อ${\displaystyle A\models \phi _{k}}$, ที่ไหน$${\displaystyle \phi _{k}:=\exists x_{1:k},\bigwedge _{1\leq i<j\leq n}E(x_{i},x_{j})}$$สิ่งนี้แสดงให้เห็นว่า ปัญหา k -clique อยู่ใน${\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 ใดๆ${\displaystyle L}$สามารถลดรูป fpt ได้อย่างง่ายดายดังนี้: แก้ปัญหา${\displaystyle (x,k)\in L}$ในเวลาแบบ fpt-time จากนั้นส่งออกวงจร Yes/No แบบง่ายๆ ที่ไม่มีการทำงานใดๆ นอกจากการส่งออกค่าบูลีนที่ถูกต้อง
• ${\displaystyle {\mathsf {FPT}}\supset W[0]}$สำหรับปัญหา W[0] ใดๆ${\displaystyle L}$และปัญหาใดๆ ก็ตาม${\displaystyle c\in L}$วงจร${\displaystyle c}$มีเส้นด้ายพุ่ง 0 เส้นและ${\displaystyle \leq d}$ความลึก ณ ที่${\displaystyle d}$มีค่าคงที่ ดังนั้นผลลัพธ์จึงถูกกำหนดโดยค่าสูงสุดถึง${\displaystyle 2^{d}}$อินพุตทั้งหมด อินพุตอื่นๆ ทั้งหมดสามารถใช้งานได้ฟรี ดังนั้นจึงสามารถคำนวณทั้งหมดโดยใช้กำลังทั้งหมดได้${\displaystyle 2^{2^{d}}}$อินพุตที่เป็นไปได้ หากอินพุตใดมีน้ำหนัก k' และทำให้เอาต์พุตของวงจรเป็น True ให้ตรวจสอบว่ายังมีอินพุตเหลือเพียงพอที่จะเติมน้ำหนักนั้นหรือไม่:${\displaystyle \#({\text{inputs of }}c)-2^{d}\geq k-k'}$.

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

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

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

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

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

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

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

ปัญหาคลิกสามารถเขียนโค้ดได้ดังนี้$${\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})}$$ฟังก์ชันนี้ตรวจสอบว่าคู่จุดยอดใดๆ ที่ไม่ได้สร้างขอบจะไม่สามารถถูกเลือกได้ ดังนั้นชุดจุดยอดใดๆ ที่ถูกเลือกจึงถูกบังคับให้เป็นกลุ่มจุดยอดที่เชื่อมต่อกัน (clique)

ปัญหาเครื่องจักรทัวริงแบบสั้นสามารถแปลงเป็นสูตรบูลีนได้โดยใช้แนวคิดการพิสูจน์แบบเดียวกับทฤษฎีบท 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ตัว${\displaystyle s_{t,i,j,a,b}}$ตั้งค่าเป็น True เพื่อระบุการเปลี่ยนสถานะของเครื่องจักรทัวริงในแต่ละครั้ง และตั้งค่า${\displaystyle k^{2}}$ตัวแปรของ${\displaystyle y_{t,p,a,b}}$ to True to indicate the tape state transition at each time. This reduces the short Turing machine problem to a problem of finding a weight-${\displaystyle (k+k^{2})}$ satisfying assignment to a weft-1, depth-2, antimonotone Boolean circuit.

W[2] problems are intuitively of the form: Guess an object of size k, perform some local processing on the object, then perform one global processing.

Examples of W[2]-complete problems include

• deciding if a given graph contains a dominating set of size k.
• deciding if a given nondeterministic multi-tape Turing machine accepts within k steps ("short multi-tape Turing machine acceptance" problem). Crucially, the branching is allowed to depend on n (like the W[1] variant), as is the number of tapes. An alternate W[2]-complete formulation allows only single-tape Turing machines, but the alphabet size may depend on n.

The dominating set problem has formula ${\displaystyle \Psi _{\text{dom}}(V,E)=\bigwedge _{u\in V}\bigvee _{v\in \operatorname {Neighbor} [u]}x_{v}}$.

Some problems are known to be W[i]-complete, though they are in a computationally generic form, and are usually studied within parameterized complexity theory itself. Empirically, as of 2013, almost all naturally-occurring parameterized problems that they have studied, turned out to be W[0]-complete, W[1]-complete, or W[2]-complete. The following are usually used:^[4]

• Weighted i-Normalized Satisfiability:^{[7][4]:Thm. 23.2.1} Given a Boolean formula, written as an AND of ORs of ANDs of ... of possibly negated variables, with ${\displaystyle i+1}$ layers of alternating ANDs or ORs, can it be satisfied by setting exactly k variables to 1?
  • Proof sketch: Any W[i]-circuit can be normalized in fpt-time by iterating association law and de Morgan distributive law, thus showing this problem is W[i]-complete.
• If i>0 is even, then
  • ${\displaystyle {\text{monotone-}}W[i]=W[i]}$.
  • Weighted Monotone i-Normalized Satisfiability is W[i]-complete.
  • Weighted Monotone (i+1)-Normalized Satisfiability is in W[i].
• If i>0 is odd, then
  • ${\displaystyle {\text{antimonotone-}}W[i]=W[i]}$
  • Weighted Antionotone i-Normalized Satisfiability is W[i]-complete.
  • If ${\displaystyle i\geq 3}$, then Weighted Antimonotone (i+1)-Normalized Satisfiability is in W[i].

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

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

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

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

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

• อินพุต: วงจรบูลีนที่มีค่า 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})}$มีนิยามดังนี้:

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

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

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