<p>The class $XP$ is the class of problems parameterized by $k$ that can be solved in time $n^{f(k)}$ for some function $f$ (each $k$ may require a different algorithm).  </p>

<p>In their book on parameterized complexity, Downey and Fellows give an example of an XP-complete problem, which is called the $(2k + 1)$-pebbling game.  The XP-hardness reduction is generic and reduces Turing machinery to this game.</p>

<p>The literature on other XP-hard problem is very sparse.
I'd like to know if there are other known XP-hard problems, perhaps that use a more natural type of reduction.</p>

CC BY-SA 3.0
2017-04-14T23:48:30.817Z
Intersection Non-emptiness for tree automata (parameterized by the number of auatomata) is an example of an XP-complete problem.  There are some parameterized pebbling problems that are known to be XP-complete as well.  I'll try to share a few references later tonight.  Thanks for asking this question.  Creating such a list would be very helpful!!  :)
Michael Wehar
CC BY-SA 3.0
2017-04-15T05:48:54.900Z
Showing that a parameterized decision problem $X$ is XP-hard is similar to proving that $X$ has a time complexity lower bound. In general, the way that you show $X$ is XP-hard is by reducing the computation of an $n^k$ time bounded Turing machine on an input of length $n$ to an instance of $f(k)$-$X$. Using the time hierarchy theorem, this is essentially the same approach for proving that $X$ has an $n^{g(k)}$ time complexity lower bound where $f(g(k)) \leq k$.
Michael Wehar
CC BY-SA 3.0
2017-04-15T05:50:19.147Z
If you happened to find the tree automata problem interesting, please let me know. I actively pursue research problems in this area and can provide some relevant references if interested.  Also, for some info and references on pebbling problems with known time complexity lower bounds, see this past stack exchange post: https://cstheory.stackexchange.com/questions/33063/are-there-more-polynomial-time-problems-with-complexity-lower-bounds
Michael Wehar
CC BY-SA 3.0
2017-04-15T05:50:59.547Z
In addition, for a couple years now, I've been seeking natural problems that are W[P]-complete. However, I've only found a few. I would be very interested in trying to build a list of W[P]-complete problems as well. :)
Michael Wehar
CC BY-SA 3.0
2017-04-16T02:21:57.650Z
@Michael Wehar : thanks for the insightful comments.  I might indeed be interested in the tree automata problem, so if you have a reference I'd gladly take it.  In fact, I'd be interested in any reference you have for other XP-completeness results, so if you have some you can provide that as an answer if you want.
Manuel Lafond
CC BY-SA 3.0
2017-04-16T05:52:45.500Z
For the tree automata problem, it was shown to be EXPTIME-complete in a paper called "On Computational Complexity of Basic Decision Problems of Finite Tree Automata".  Then, I wrote a paper with a friend showing that when parameterized by the number of automata, this problem cannot be solved in less than $n^{\Omega(k)}$ time.  This paper is titled "On the Complexity of Intersecting Regular, Context-free, and Tree Languages".  Finally, in my dissertation titled "On the Complexity of Intersection Non-Emptiness Problems", I included that this problem is $XP$-complete.
Michael Wehar
CC BY-SA 3.0
2017-04-16T05:55:05.763Z
I wish I had some more references to other people's work, but I'm in the same boat as you.  I'm trying to find other problems that are known to be $XP$-complete.  :)
Michael Wehar
CC BY-SA 4.0
2018-06-06T18:11:06.080Z
@user124864 This is great!!  I didn't know about the $W[P]$ complete problem that you mentioned.  Could you possibly provide a reference.  I would very much like to learn more about it.  :)
Michael Wehar
CC BY-SA 4.0
2018-06-06T18:25:04.540Z
@user124864 For XP complete problems, I wish I had some other references, but the only XP complete problems that I can think of are emptiness problems for automata, pebbling problems, and machine simulations problems.
Michael Wehar
CC BY-SA 4.0
2018-06-06T20:02:32.080Z
@user124864 Thank you very much!!  :)
Michael Wehar
CC BY-SA 4.0
2018-06-06T21:40:09.893Z
@user124864 I will look into this.  Thanks for sharing!!  :)
Michael Wehar
CC BY-SA 4.0
2018-06-08T18:59:41.353Z
@user124864 Haven't yet had a chance to look into your queries, but I hope to this weekend.  :)
Michael Wehar
CC BY-SA 4.0
2020-04-08T16:51:43.030Z
I recently found a paper that lists P-complete problems.  Maybe some of them can be generalized to XP-complete parameterized problems.  See here: https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.31.2644
Michael Wehar
CC BY-SA 4.0
2022-09-29T15:44:41.230Z
Recently the following paper was shared with me that suggests a new W[P]-complete problem. I thought that this might be relevant. :)
Michael Wehar
CC BY-SA 4.0
2022-09-29T15:45:05.273Z
See here: https://link.springer.com/article/10.1007/s10458-022-09578-2
Michael Wehar
CC BY-SA 4.0
2023-05-12T20:59:02.777Z
@Michael Wehar : while searching for W[P]-complete problems, I ended up here and I just saw that you added comments to this.  Thanks for sharing, again!  Also, in case you have the answer, a question here asks for the W classification problem for partial set cover, where the difficulty is making a circuit is that one must count the number of covered elements: https://cstheory.stackexchange.com/questions/52821/wt-containment-of-partial-covering-problems
Manuel Lafond
CC BY-SA 4.0
2023-05-13T15:21:29.400Z
Thank you very much for sharing this!!  :)
Michael Wehar
<reductions><parameterized-complexity>
A list of XP-hard problems
Manuel Lafond
# A list of XP-hard problems

(Asked by: username_0 on 2017-04-14)

The class $XP$ is the class of problems parameterized by $k$ that can be solved in time $n^{f(k)}$ for some function $f$ (each $k$ may require a different algorithm).

In their book on parameterized complexity, Downey and Fellows give an example of an XP-complete problem, which is called the $(2k + 1)$-pebbling game. The XP-hardness reduction is generic and reduces Turing machinery to this game.

The literature on other XP-hard problem is very sparse.
I'd like to know if there are other known XP-hard problems, perhaps that use a more natural type of reduction.

**Tags:** reductions, parameterized-complexity
> **Comments:**
> **username_1**: Intersection Non-emptiness for tree automata (parameterized by the number of auatomata) is an example of an XP-complete problem.  There are some parameterized pebbling problems that are known to be XP-complete as well.  I'll try to share a few references later tonight.  Thanks for asking this question.  Creating such a list would be very helpful!!  :)  
> **username_1**: Showing that a parameterized decision problem $X$ is XP-hard is similar to proving that $X$ has a time complexity lower bound. In general, the way that you show $X$ is XP-hard is by reducing the computation of an $n^k$ time bounded Turing machine on an input of length $n$ to an instance of $f(k)$-$X$. Using the time hierarchy theorem, this is essentially the same approach for proving that $X$ has an $n^{g(k)}$ time complexity lower bound where $f(g(k)) \leq k$.  
> **username_1**: If you happened to find the tree automata problem interesting, please let me know. I actively pursue research problems in this area and can provide some relevant references if interested.  Also, for some info and references on pebbling problems with known time complexity lower bounds, see this past stack exchange post: https://cstheory.stackexchange.com/questions/33063/are-there-more-polynomial-time-problems-with-complexity-lower-bounds  
> **username_1**: In addition, for a couple years now, I've been seeking natural problems that are W[P]-complete. However, I've only found a few. I would be very interested in trying to build a list of W[P]-complete problems as well. :)  
> **username_0**: @Michael Wehar : thanks for the insightful comments.  I might indeed be interested in the tree automata problem, so if you have a reference I'd gladly take it.  In fact, I'd be interested in any reference you have for other XP-completeness results, so if you have some you can provide that as an answer if you want.  
> **username_1**: For the tree automata problem, it was shown to be EXPTIME-complete in a paper called "On Computational Complexity of Basic Decision Problems of Finite Tree Automata".  Then, I wrote a paper with a friend showing that when parameterized by the number of automata, this problem cannot be solved in less than $n^{\Omega(k)}$ time.  This paper is titled "On the Complexity of Intersecting Regular, Context-free, and Tree Languages".  Finally, in my dissertation titled "On the Complexity of Intersection Non-Emptiness Problems", I included that this problem is $XP$-complete.  
> **username_1**: I wish I had some more references to other people's work, but I'm in the same boat as you.  I'm trying to find other problems that are known to be $XP$-complete.  :)  
> **username_1**: @user124864 This is great!!  I didn't know about the $W[P]$ complete problem that you mentioned.  Could you possibly provide a reference.  I would very much like to learn more about it.  :)  
> **username_1**: @user124864 For XP complete problems, I wish I had some other references, but the only XP complete problems that I can think of are emptiness problems for automata, pebbling problems, and machine simulations problems.  
> **username_1**: @user124864 Thank you very much!!  :)  
> **username_1**: @user124864 I will look into this.  Thanks for sharing!!  :)  
> **username_1**: @user124864 Haven't yet had a chance to look into your queries, but I hope to this weekend.  :)  
> **username_1**: I recently found a paper that lists P-complete problems.  Maybe some of them can be generalized to XP-complete parameterized problems.  See here: https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.31.2644  
> **username_1**: Recently the following paper was shared with me that suggests a new W[P]-complete problem. I thought that this might be relevant. :)  
> **username_1**: See here: https://link.springer.com/article/10.1007/s10458-022-09578-2  
> **username_0**: @Michael Wehar : while searching for W[P]-complete problems, I ended up here and I just saw that you added comments to this.  Thanks for sharing, again!  Also, in case you have the answer, a question here asks for the W classification problem for partial set cover, where the difficulty is making a circuit is that one must count the number of covered elements: https://cstheory.stackexchange.com/questions/52821/wt-containment-of-partial-covering-problems  
> **username_1**: Thank you very much for sharing this!!  :)  

---

## 0 answers

