Timeline for Reducing Parameterized Problems (whose solution size can be "large") to W[i]-complete problems (for fixed i)
Current License: CC BY-SA 4.0
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 18, 2020 at 11:29 | history | bounty ended | Haden Hooyeon Lee | ||
| Nov 18, 2020 at 11:29 | vote | accept | Haden Hooyeon Lee | ||
| Nov 13, 2020 at 12:28 | comment | added | Haden Hooyeon Lee | Yes, I can ask about it as a new question, but I also wanted to related it to my original question; specifically this part: "I'm curious how one can show that X is in W[1] or W[2], e.g., when the size of a solution can still be "n" yet we can only choose "k" input gates as it seems impossible (how could you encode a large solution using only a (fixed) number of bits?). Even though X is known to be W[1]-hard or W[2]-hard, it may actually require circuits with large wefts than 2, for instance, if completeness is not known yet." The concrete question fits this, doesn't it? | |
| Nov 13, 2020 at 10:50 | comment | added | Christian Komusiewicz | I like the new part of the question but isn't this a new question? It asks for a concrete problem whether one can show containment in W[2] or hardness for W[3]. This differs a a bit from the original question. | |
| Nov 13, 2020 at 9:46 | comment | added | Haden Hooyeon Lee | Thanks for the first answer! After reading your answer, I think I can better explain exactly what I am after using a specific problem and the issues I ran into. I just added the details to the original post as it would exceed the character limit of a comment... | |
| Nov 12, 2020 at 12:27 | history | answered | Christian Komusiewicz | CC BY-SA 4.0 |