參數複雜性

在計算機科學中，參數複雜性^[1]（英語：parameterized complexity，存在其他譯法）是計算複雜性理論的一個分支，其側重使用與輸入輸出有關的參數去區分並解決各種運算問題。具體來說，其會將問題轉化，使得存在一個複雜度包含上述參數的函數。

假設P≠NP，那麼就會有很多問題的時間複雜度並非線性，但通過上述轉化，可以得到一種函數，其總複雜度與參數k呈指數關係且與輸入規模呈線性關係。因此，如果k能夠被固定在一個比較小的範圍內，且其關於k的增長並不那麼迅速，那麼這類問題仍然可被認為是可解的，儘管傳統意義上這些問題仍是不可解的。

這類存在參數k的問題被稱為「參數化問題」，而能夠設計出對應函數求解的參數化問題被稱為「固定參數可解」（英語：fixed-parameter tractable，FPT）的問題^[2]。

一般轉化後的問題形式如下：給定一個物體x，一個非負整數k，x中是否存在某些性質取決於k？比如說，在點覆蓋問題中，k可以是點的個數。在實際應用中，一般會假設k比輸入規模或者某個輸入要小。在這種情況下，找到一個僅與k非多項式複雜度（而非與輸入規模的非多項式複雜度）有關的算法便是核心所在，但這比較具有挑戰性。