參數化的複雜性

在計算機科學中，參數化的複雜性是計算複雜性理論的一個分支，該分支側重於計算問題根據輸入或輸出的多個參數對其固有的困難進行分類。然後將問題的複雜性作為這些參數的函數測量。這允許比經典環境更細微的規模分類NP問題，在經典環境中，問題的複雜性僅作為輸入中的位數的函數來測量。這似乎是在Gurevich，Stockmeyer＆Vishkin（1984）中首次證明的。關於參數化複雜性的第一項系統工作是由Downey＆Fellows（1999）完成的。

在假設p≠np的假設下，存在許多自然問題，這些問題需要超級物質運行時間，而僅根據輸入大小來衡量複雜性，但可以在輸入大小和指數中多項式的時間內計算，或在參數中更糟k 。因此，如果k固定為較小的值，並且函數在k上的增長相對較小，那麼儘管它們的傳統分類為“棘手”，但仍然可以將這些問題視為“可拖動”。

如果未固定輸入參數，則存在有效，精確和確定性求解算法，或者其他NP-HARD的存在，如果輸入參數未固定；這些問題的所有已知求解算法都需要輸入總大小的時間（尤其是超級單位）。但是，某些問題可以通過僅以固定參數的大小為指數的算法來解決，而多項式的輸入大小。這種算法稱為固定參數可拖動（FPT）算法，因為對於固定參數的恆定值，可以有效地解決問題（即，在多項式時間）。

固定某些參數k的問題稱為參數化問題。一個允許這種FPT算法的參數化問題被認為是固定參數可進行的問題，並且屬於類FPT ，並且參數化複雜性理論的早期名稱是固定參數的障礙性。

許多問題具有以下形式：給定對象X和一個非負整數K ， X是否具有取決於K的某些屬性？例如，對於頂點覆蓋問題，參數可以是封面中的頂點數。在許多應用程序中，例如，在建模誤差校正時，與總輸入大小相比，可以假設參數為“小”。然後，找到僅在k中而不是輸入大小的指數級的​​算法是一個挑戰。

這樣，參數化的複雜性就可以看作是二維複雜性理論。該概念正式化如下：

一個參數化的問題是一種語言 ， 在哪裡是有限字母。第二個組件稱為問題的參數。
參數化的問題L如果問題是固定參數，則可以進行固定參數。 ？”可以在跑步時間決定 ，其中f僅取決於k 。相應的複雜性類稱為fpt 。

例如，有一種算法解決了頂點覆蓋問題時間， n是頂點的數量， k是頂點蓋的大小。這意味著頂點蓋是固定參數，可將解決方案的大小作為參數。

複雜性類

fpt

FPT包含固定參數可處理問題，這些問題是可以隨時間解決的對於某些可計算功能f 。通常，此功能被認為是單個指數，例如 ，但是定義承認的功能甚至更快。這對於該課程的早期歷史的很大一部分至關重要。定義的關鍵部分是排除表單的功能 ， 例如 。

類FPL類（固定參數線性）是可以在時間上解決的問題類對於某些可計算功能f 。因此，FPL是FPT的子類。一個示例是布爾滿意度問題，該問題由變量數量參數。可以通過蠻力在時間上檢查帶有K變量的大小m的給定公式 。在序列n的圖中，大小為k的頂點蓋可以在及時找到 ，因此頂點覆蓋問題也在FPL中。

一個被認為不在fpt的問題的示例是通過顏色數量來參數的圖形著色。眾所周知，3色是NP-HARD ，並且是圖形k顏色的算法為了將以輸入大小的多項式時間運行。因此，如果圖形著色以顏色的數量參數為fpt，則p = np 。

FPT有許多替代定義。例如，運行時間要求可以取代 。另外，如果它具有所謂的內核，則在fpt中存在一個參數化的問題。內核化是一種預處理技術，可將原始實例降低到其“硬內核”，一個可能相當於原始實例的實例，但具有由參數中的函數界定的大小。

FPT在降低的參數化概念中封閉，稱為fpt-reductions 。這樣的減少改變了實例在等效實例中的一些問題另一個問題（與 ），可以在時間計算在哪裡是多項式。

顯然，FPT包含所有多項式計算問題。此外，它包含NP中的所有優化問題，允許有效的多項式時間近似方案（EPTA） 。

w層次結構

W層次結構是計算複雜性類的集合。如果每個實例可以（以FPT時間）轉換為最多具有緯線的組合電路，以便當且僅當對將1分配給k個輸入分配1的輸入的分配令人滿意的情況下。在從輸入到輸出的任何路徑上，緯線是最大數量的邏輯單元。路徑（稱為深度）上邏輯單元的總數必須受到所有問題的常數的限制。

注意和對全部 。 W層次結構中的類也在降低FPT-RECL-RECLED下關閉。

W [ i ]的一個完整問題是加權i-肯定的滿意度：給定一個布爾公式，以否定變量為and and ... Ands或ORS（以及I之間和OR之間的我的交替），可以通過將k變量精確設置為1來滿足嗎？

許多自然計算問題佔據了較低的水平， W [1]和W [2]。

W [1]

w [1] - 完整問題的示例包括

  • 確定給定圖是否包含大小k的庫
  • 確定給定圖是否包含獨立的大小k
  • 確定給定的非確定性單錄像機是否在K步驟內接受（“短圖裡機器接受”問題）。這也適用於帶有F （ k ）磁帶的非確定性圖靈機，甚至是F （ k ）維磁帶的F （ k ），但即使有此擴展名，限制了F （ k ）膠帶字母尺寸的限制是固定參數tractameter tractableable。至關重要的是，允許每個步驟的圖靈機的分支依賴於n ，即輸入的大小。通過這種方式，圖靈機可以探索N o（ k ）計算路徑。

W [2]

w [2] - 完整問題的示例包括

  • 確定給定圖是否包含一個主導尺寸K
  • 確定給定的非確定性多錄像機是否在k步中接受（“短多磁帶圖靈機的接受”問題）。至關重要的是，允許分支依賴於n （如w [1]變體），磁帶數也是如此。替代W [2] - 拼寫公式僅允許單束通風機，但字母大小可能取決於n 。

w [ t ]

可以使用加權緯度的家族來定義 ： 是將這個問題降低到這個問題的一類參數化問題，並且 。

在這裡，加權的緯線- t -depth- d sat是以下問題：

  • 輸入：最多最多d和緯度的布爾公式，最多是t ，一個數字k 。深度是從根到葉的任何路徑上的最大門數，緯線是從根到葉子的任何路徑上至少三個路徑的扇形門的最大門。
  • 問題：該公式是否完全可以完成錘子的重量k ？

可以證明問題加權t-納向sat已完成在降低FPT下。在這裡，加權t-納向SAT是以下問題：

  • 輸入：最多的布爾公式，最多是頂部的t和gate，一個數字k 。
  • 問題：該公式是否完全可以完成錘子的重量k ？

W [ P ]

W [ P ]是可以由非確定性決定的問題類別 - 最多製造的Turing Machine 計算中的無確定選擇 （一台由K限制的圖靈機）。 Flum＆Grohe（2006）

眾所周知，fpt包含在w [p]中，並且納入被認為是嚴格的。但是，解決此問題將意味著解決P與NP問題的解決方案。

與未參數的計算複雜性的其他連接是，當且僅當電路可滿足時，FPT等於w [ p ] ，或者僅當並且只有存在可計算的，無核的，無限的函數f，以便使用非確定的多項式時間Turing Machine使用的所有語言使用無確定的選擇在p中。

w [ p ]可以鬆散地認為是我們有一組n個項目的問題類別，我們想找到一個子集大小為k ，使某個屬性擁有。我們可以將選擇作為k整數列表進行編碼，該列表存儲在二進制中。由於這些數字中的最高都可以是n ， 每個數字都需要位。所以需要總數來編碼選擇。因此，我們可以選擇一個子集和無確定的選擇。

XP

XP是可以在時間上解決的參數化問題類別對於某些可計算功能f 。這些問題稱為切片多項式，從某種意義上說，固定k的每個“切片”都有一個多項式算法，儘管每個k的指數可能具有不同的指數。將其與FPT進行比較，FPT僅允許每個值的每個值都有不同的常數預成型。 XP包含FPT，眾所周知，這種遏制是嚴格的對角線化。

para-np

para-np是一類參數化問題，可以通過不確定性算法解決的參數化問題對於某些可計算功能f 。眾所周知當且只有 。

一個問題是para-np-hard如果是 -HARD為參數的常數值。也就是說，有一個固定k的“切片”是 -難的。一個參數化的問題是 -HARD不能屬於班級 ， 除非 。一個經典的例子 - hard參數化問題是圖形著色，由顏色的數字k進行了參數，已經 - hard （請參閱圖形＃計算複雜性）。

層次結構

A層次結構是類似於W層次結構的計算複雜性類的集合。但是，儘管W層次結構是NP中包含的層次結構，但A層次結構更緊密地模仿經典複雜性的多項式層次結構。眾所周知，a [1] = w [1]持有。

也可以看看