1
$\begingroup$
  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).

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thank you for the detailed explanation. So is parametrized ILP in FPP or in FPT? $\endgroup$ – Problem Jul 13 '17 at 11:10

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.