Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
On page 33 venn diagram in http://tcs.rwth-aachen.de/~sanchez/slides/Raleigh2014.pdf it is implied that $XP\subseteq NP$.
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?
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).
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.
