Timeline for NP-hardness of a string transformation problem with k templates
Current License: CC BY-SA 4.0
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 8 at 16:56 | comment | added | kodlu | Well, computing the edit distance (levenshtein distance) is NP complete so this may be as well. See cstheory.stackexchange.com/questions/47899/… | |
| May 1 at 16:47 | comment | added | Paul Calvi | Yes, $k$ is the number of different templates that you are going to use. You can use them as much as you want and in the order that you want. | |
| May 1 at 16:27 | comment | added | QC_QAOA | Can you 'reuse' the templates after you've used them once already? IE $x=AAAA$, $y=BCBC$, $l=2$ and $k=1$. Then you can with the template $BC$ if you can use it twice. | |
| May 1 at 15:50 | comment | added | Paul Calvi | Yes $X$ and $Y$ are the same length otherwise the problem is not solvable. I'm just interested in showing that it is NP-hard to decide if for an instance $(x, y, l, k)$ it is possible to apply the transformation describe above to go from $x$ to $y$. | |
| Apr 30 at 20:07 | comment | added | Bill Bradley | I take it that $X$ and $Y$ are the same length? I think you also need to specify the length $|X|=n$, and the alphabet size $|\mathcal{A}|=a$, which I guess you take to be 26 here. With all that specified, are you interested in the situation where all of those variables might change, or in the case where only $n$ grows but (for example) $l$ is constant? | |
| Apr 30 at 16:16 | comment | added | Paul Calvi | I've edited the message to add clarification on the use of templates and the transformation process. I hope it's clearer now. | |
| Apr 30 at 16:15 | history | edited | Paul Calvi | CC BY-SA 4.0 |
Precised the use of templates
|
| Apr 29 at 14:20 | review | Close votes | |||
| May 10 at 3:08 | |||||
| Apr 29 at 11:57 | comment | added | Daniel Weber | Could you define what are templates and how you do the transformation? | |
| S Apr 29 at 9:42 | review | First questions | |||
| Apr 29 at 11:49 | |||||
| S Apr 29 at 9:42 | history | asked | Paul Calvi | CC BY-SA 4.0 |