الگوریتم های با پارامتر ثابت

اگر پارامتر k را هم به ازای ورودی ها داشته باشیم (به جز n که سایز ورودی است) می توانیم الگوریتم هایی با زمان O(f(k)n^c) بدهیم که در آنها c ثابت است. به چنین الگوریتمی پارامتر ثابت (fixed parameter) می گویند. در الگوریتم k را ثابت فرض می کنیم.

http://www.cs.bme.hu/~dmarx/papers/marx-tractability-slides.pdf

اگر برای مساله ی np-complete بتوانیم پارامتر ثابت k تعیین کنیم که به ازای آن الگوریتم بر حسب k نمایی باشد و برحسب n چند جمله ای باشد به آن FPC می گویند. (مخفف fixed parameter tractable)

http://en.wikipedia.org/wiki/Parameterized_complexity