Timeline for A list of XP-hard problems
Current License: CC BY-SA 3.0
19 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 13, 2023 at 15:21 | comment | added | Michael Wehar | Thank you very much for sharing this!! :) | |
| May 12, 2023 at 20:59 | comment | added | Manuel Lafond | @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: cstheory.stackexchange.com/questions/52821/… | |
| Sep 29, 2022 at 15:45 | comment | added | Michael Wehar | See here: link.springer.com/article/10.1007/s10458-022-09578-2 | |
| Sep 29, 2022 at 15:44 | comment | added | Michael Wehar | Recently the following paper was shared with me that suggests a new W[P]-complete problem. I thought that this might be relevant. :) | |
| Apr 8, 2020 at 16:51 | comment | added | Michael Wehar | I recently found a paper that lists P-complete problems. Maybe some of them can be generalized to XP-complete parameterized problems. See here: citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.31.2644 | |
| Jun 8, 2018 at 18:59 | comment | added | Michael Wehar | @user124864 Haven't yet had a chance to look into your queries, but I hope to this weekend. :) | |
| Jun 6, 2018 at 21:40 | comment | added | Michael Wehar | @user124864 I will look into this. Thanks for sharing!! :) | |
| Jun 6, 2018 at 20:02 | comment | added | Michael Wehar | @user124864 Thank you very much!! :) | |
| Jun 6, 2018 at 18:25 | comment | added | Michael Wehar | @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. | |
| Jun 6, 2018 at 18:11 | comment | added | Michael Wehar | @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. :) | |
| Apr 16, 2017 at 5:55 | comment | added | Michael Wehar | 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. :) | |
| Apr 16, 2017 at 5:52 | comment | added | Michael Wehar | 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. | |
| Apr 16, 2017 at 2:21 | comment | added | Manuel Lafond | @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. | |
| Apr 15, 2017 at 15:09 | history | tweeted | twitter.com/StackCSTheory/status/853264008199241728 | ||
| Apr 15, 2017 at 5:50 | comment | added | Michael Wehar | 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. :) | |
| Apr 15, 2017 at 5:50 | comment | added | Michael Wehar | 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: cstheory.stackexchange.com/questions/33063/… | |
| Apr 15, 2017 at 5:48 | comment | added | Michael Wehar | 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$. | |
| Apr 14, 2017 at 23:48 | comment | added | Michael Wehar | 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!! :) | |
| Apr 14, 2017 at 19:35 | history | asked | Manuel Lafond | CC BY-SA 3.0 |