1. On page 33 venn diagram in http://tcs.rwth-aachen.de/~sanchez/slides/Raleigh2014.pdf it is implied that $XP\subseteq NP$.

  2. Below this there is a statement which says $XP\not = NP$ unless $P=NP$.

Is there a reference for proof for these two $XP$ statements?

  • 5
    $\begingroup$ XP is a parameterized complexity class while NP is a complexity class. There are multiple ways of defining what a parameterized problem is, but I would take the stance that a parameterized problem has a different type than a decision problem. As a result, XP contains different kinds of things than NP making them incompatible. $\endgroup$ – Michael Wehar Jun 21 '17 at 20:59
  • 1
    $\begingroup$ Let me elaborate. Clique is an NP-complete decision problem. When one says $k$-clique, one typically is referring to a particular parameterization of the clique problem where $k$ may or may not be a fixed value for the parameter. The Clique problem along with this parameterization would make a parameterized problem. There could be many alternative parameterizations of the Clique problem that would give distinct parameterized problems. $\endgroup$ – Michael Wehar Jun 21 '17 at 21:05
  • 1
    $\begingroup$ That being said, I enjoyed taking a look at the slides that you shared. They are neat! :) $\endgroup$ – Michael Wehar Jun 21 '17 at 23:13

On the first question:

First off, I do not think the statement $\mathsf{XP} \subseteq \mathsf{NP}$ is meant to be implied at that point. To explain what is meant, let me ask a question: What is the parameterized counterpart to $\mathsf{NP}$?

This question naturally arises when defining a notion of intractability of parameterized problems as classical intractabilty is thought to correspond with $\mathsf{NP}$-hardness. A first attempt yields $\mathsf{ParaNP}$, basically a nondeterministic $\mathsf{FPT}$, but a theorem states that if some parameterized problem $(L, \kappa)$ is $\mathsf{ParaNP}$-complete, then already a finite union of slices (the $k$th slice of $(L,\kappa)$ is the set of instances $x$ in $L$ of parameter $\kappa(x) = k$) is already $\mathsf{NP}$-complete and thus all the hardness is already exhibited by some parameter values. Conversely, it means that problems whose slices (for fixed $k$) are solvable in polynomial time are not $\mathsf{ParaNP}$-hard -- thus this class does not yield hardness results for problems like SAT (parameterized by the number of variables), $k$-Clique (parameterized by the size of the solutions) and many other problems which are believed not to be in $\mathsf{FPT}$.

Now, (uniform) $\mathsf{XP}$ deals exactly with this kind of problems whose slices are in $\mathsf{P}$, but the definition allows for very large running times if the parameters get large w.r.t. the input size and indeed, if we parameterize by the input length, we can use exponential time algorithms and as such, $\mathsf{XP}$ contains problems from $\mathsf{EXP}$ using some suitable parameterization, but not problems like $k$-Colorabilty parameterized by $k$.

So neither $\mathsf{ParaNP}$ nor $\mathsf{XP}$ are the class that we sought out to find and in this light, we can (sort of) understand that slide as an attempt to partition the landscape of $\mathsf{NP}$ problems and their parameterized versions into somewhat meaningful parameterized complexity classes (however, it suggests $\mathsf{XP} \subseteq \mathsf{ParaNP}$ which is not the case).

On the second question:

Arguably, one can interpret the statement $\mathsf{XP} = \mathsf{NP}$ to mean that "the class of unparameterized versions of the naturally parameterized problems in $\mathsf{XP}$ coincides with $\mathsf{NP}$" and since membership in $\mathsf{XP}$ means that the slices of a problem are in $\mathsf{P}$, we get that unless $\mathsf{P} = \mathsf{NP}$ there exist some problems in $\mathsf{NP}$ which are not in $\mathsf{XP}$ when using some parameterizations (like $k$-Colorability parameterized by $k$) and thus falsifying our interpretation of $\mathsf{XP} = \mathsf{NP}$.

This of course is a bit speculative, but given that one class is parameterized while the other is not together with the results we have seen, I have no better interpretation to give.


M. Grohe, J. Flum: Parameterized Complexity Theory

  • $\begingroup$ Does $ParaNP=XP\implies NP=EXP$ and/or vice versa? $\endgroup$ – T.... May 22 at 11:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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