<p>You're confusing decision problems (in the classical sense) with parameterized decision problems. Classical decision problems are subsets of $\Sigma^*$, whereas parameterized decision problems are often considered as subsets of $\Sigma^* \times \mathbb{N}$ (see [1, Chapter 2]). Classical complexity classes (such as NC, P and NP) are sets of classical decision problems, and parameterized complexity classes (such as FPT) are sets of parameterized decision problems.
(If $Q \subseteq \Sigma^* \times \mathbb{N}$ is a parameterized decision problem, then the unparameterized version of $Q$ denotes the classical decision problem $Q' = \{ x\ |\ (x,k) \in Q \}$.)</p>

<p>Integer linear programming (ILP) is a classical decision problem (that is, the variant you're referring to: deciding whether there exists a feasible integer solution that achieves at least a certain value of the objective function). If you consider a parameterized variant of this problem (e.g., when taking as parameter the number of variables), it is a parameterized decision problem. So asking whether the problem of ILP parameterized by the number of variables is P-complete or in NC does not make sense. What you should be asking is whether it is complete for a parameterized analogue of P, or whether it is contained in a parameterized analogue of NC.</p>

<p>The parameterized complexity class FPT (consisting of all parameterized decision problems that are fixed-parameter tractable) is the parameterized analogue of P. One possible appropriate parameterized analogue of NC is the parameterized complexity class FPP (see [2]). FPP consists of all parameterized decision problems that are solvable in time $f(k) \cdot (\log n)^c$ by a parallel algorithm with at most $f(k) \cdot n^c$ processors, for some computable function $f$ and some constant $c$, where $n$ is the input size and $k$ is the parameter value.</p>

<p>To answer question (2): an example of a parameterized decision problem that is FPT-complete and whose unparameterized version is NP-complete, is the problem of satisfiability of propositional logic formulas in CNF, parameterized by the size of the smallest strong backdoor to Horn (see, e.g., [3]). Essentially, this problem is FPT-complete (under an appropriate parameterized variant of log-space reductions) because satisfiability for propositional Horn formulas is P-complete (under log-space reductions).</p>

<p>For any NP-complete decision problem, you can come up with a parameterized version that is in FPP: take as parameter the size of the input. Then the problem is (trivially) solvable in time $f(k)$ (for some exponential function $f$) on a single processor. Basically, such an algorithm can solve the problem in brute force in time $f(k)$. You're probably asking for natural parameterized variants of NP-complete problems that are in FPP.</p>

<h3>References</h3>

<p>[1] Downey, Rodney G., and Michael R. Fellows. <i>Fundamentals of parameterized complexity</i>. Springer, 2013.</p>

<p>[2] Cesati, Marco, and Miriam Di Ianni. <i>Parameterized parallel complexity.</i> European Conference on Parallel Processing. Springer, Berlin, Heidelberg, 1998.</p>

<p>[3] Gaspers, Serge, and Stefan Szeider. <i>Backdoors to satisfaction.</i> In: The Multivariate Algorithmic Revolution and Beyond. Pages 287-317. Springer, 2012.</p>

CC BY-SA 3.0
2017-07-13T11:10:44.807Z
Thank you for the detailed explanation. So is parametrized ILP in FPP or in FPT?
Turbo
CC BY-SA 3.0
2017-07-13T09:13:46.520Z
2017-07-13T09:13:46.520Z
Ronald de Haan
<ol>
<li><p>Integer programming is $NP$ complete however fixed parameter tractable in number of variables. Is the fixed parameter version in parametrized analogue of $P$-complete or in parametrized analogue of $NC$? (<strong>Update</strong>: It is not known)</p></li>
<li><p><s> What are some examples of problems that are $NP$ complete but whose fixed parameter version is in parametrized analogue of $P$ and provably in parametrized analogue of $P$ complete and problems that are $NP$ complete but whose fixed parameter version is in parametrized analogue of $P$ and provably in parametrized analogue of $NC$? Is there a theory behind such classification?</s> (resolved by Ronald de Haan).</p></li>
</ol>

<cc.complexity-theory><big-picture><np-complete><integer-programming><fixed-parameter-tractable>
Fixed parameter tractable Integer Programming and $FPP$
Turbo
# Fixed parameter tractable Integer Programming and $FPP$

(Asked by: username_0 on 2017-07-13)

1. Integer programming is $NP$ complete however fixed parameter tractable in number of variables. Is the fixed parameter version in parametrized analogue of $P$-complete or in parametrized analogue of $NC$? (**Update**: It is not known)
2. ~~What are some examples of problems that are $NP$ complete but whose fixed parameter version is in parametrized analogue of $P$ and provably in parametrized analogue of $P$ complete and problems that are $NP$ complete but whose fixed parameter version is in parametrized analogue of $P$ and provably in parametrized analogue of $NC$? Is there a theory behind such classification?~~ (resolved by Ronald de Haan).

**Tags:** cc.complexity-theory, big-picture, np-complete, integer-programming, fixed-parameter-tractable

---

## 1 answers

### Answer by username_1 on 2017-07-13. Score: 6 | Accepted answer

You're confusing decision problems (in the classical sense) with parameterized decision problems. Classical decision problems are subsets of $\Sigma^\*$, whereas parameterized decision problems are often considered as subsets of $\Sigma^\* \times \mathbb{N}$ (see [1, Chapter 2]). Classical complexity classes (such as NC, P and NP) are sets of classical decision problems, and parameterized complexity classes (such as FPT) are sets of parameterized decision problems.
(If $Q \subseteq \Sigma^\* \times \mathbb{N}$ is a parameterized decision problem, then the unparameterized version of $Q$ denotes the classical decision problem $Q' = \{ x\ |\ (x,k) \in Q \}$.)

Integer linear programming (ILP) is a classical decision problem (that is, the variant you're referring to: deciding whether there exists a feasible integer solution that achieves at least a certain value of the objective function). If you consider a parameterized variant of this problem (e.g., when taking as parameter the number of variables), it is a parameterized decision problem. So asking whether the problem of ILP parameterized by the number of variables is P-complete or in NC does not make sense. What you should be asking is whether it is complete for a parameterized analogue of P, or whether it is contained in a parameterized analogue of NC.

The parameterized complexity class FPT (consisting of all parameterized decision problems that are fixed-parameter tractable) is the parameterized analogue of P. One possible appropriate parameterized analogue of NC is the parameterized complexity class FPP (see [2]). FPP consists of all parameterized decision problems that are solvable in time $f(k) \cdot (\log n)^c$ by a parallel algorithm with at most $f(k) \cdot n^c$ processors, for some computable function $f$ and some constant $c$, where $n$ is the input size and $k$ is the parameter value.

To answer question (2): an example of a parameterized decision problem that is FPT-complete and whose unparameterized version is NP-complete, is the problem of satisfiability of propositional logic formulas in CNF, parameterized by the size of the smallest strong backdoor to Horn (see, e.g., [3]). Essentially, this problem is FPT-complete (under an appropriate parameterized variant of log-space reductions) because satisfiability for propositional Horn formulas is P-complete (under log-space reductions).

For any NP-complete decision problem, you can come up with a parameterized version that is in FPP: take as parameter the size of the input. Then the problem is (trivially) solvable in time $f(k)$ (for some exponential function $f$) on a single processor. Basically, such an algorithm can solve the problem in brute force in time $f(k)$. You're probably asking for natural parameterized variants of NP-complete problems that are in FPP.

### References

[1] Downey, Rodney G., and Michael R. Fellows. *Fundamentals of parameterized complexity*. Springer, 2013.

[2] Cesati, Marco, and Miriam Di Ianni. *Parameterized parallel complexity.* European Conference on Parallel Processing. Springer, Berlin, Heidelberg, 1998.

[3] Gaspers, Serge, and Stefan Szeider. *Backdoors to satisfaction.* In: The Multivariate Algorithmic Revolution and Beyond. Pages 287-317. Springer, 2012.

> **Comments:**
> **username_0**: Thank you for the detailed explanation. So is parametrized ILP in FPP or in FPT?  

---

