Timeline for NP-hardness of a sequence problem
Current License: CC BY-SA 4.0
26 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 31, 2020 at 4:12 | comment | added | Ville Salo | Well, maybe ask it separately, as has been suggested? | |
| Jul 31, 2020 at 2:17 | comment | added | lchen | @VilleSalo I am inclined to say that $T=O(n^2)$ seems to be the lower-bound, $O(n)$ seems not achievable. | |
| Jul 29, 2020 at 7:26 | vote | accept | lchen | ||
| Jul 28, 2020 at 16:51 | comment | added | Ville Salo | FWIW, I'm pretty sure my $T = O(n^2)$ is not optimal (and I conjecture that @fedja has a $T = O(n)$ construction). | |
| Jul 28, 2020 at 15:24 | comment | added | fedja | @Ichen Your are welcome, of course, but my main point was to ask if you are really interested in the efficient design of such codes (I.e., minimizing $T$, given $n$) rather than in the problem you posted. If you are, you are welcome to ask a separate question to that extent. My construction was pretty close to Ville's though I made some steps a bit differently (it is the same encoding with the same 2 extra precautions: bounding the shifts and making sure that only one user can be blocked). | |
| Jul 28, 2020 at 7:11 | comment | added | Ville Salo | I agree with @fedja that if you want to find such a code, then you could've just asked for such a code. If you need many such codes, or are not sure yet what kind of additional properties you want for the codes, then it's useful to know the problem is in co-NP because computers are good at solving problems in co-NP. Knowing it's co-NP-complete is useful because it means you're not missing an obvious polynomial-time algorithm, unless we all are. | |
| Jul 28, 2020 at 7:05 | answer | added | Ville Salo | timeline score: 5 | |
| Jul 28, 2020 at 4:15 | comment | added | lchen | @fedja Thank you for your comments. | |
| Jul 27, 2020 at 23:20 | comment | added | fedja | Isn't "We want to design a code for each of the $n$ users." + " We want to check whether a set of codes can ensure that..." equal to "For what $T$ and $n$ can we design a set of codes such that ... and how to do it?". If this equality holds, the question should, probably, be asked quite differently (indeed, why should you care whether some set of codes designed not by you is good or not if you can just set up the codes yourself?). And yes, one can easily reduce 3-SAT to your current problem, but Ville was the first to note that, so I'll leave the honor to him :-) | |
| Jul 27, 2020 at 15:50 | comment | added | Ville Salo | I suppose I have at least a direct reduction from $3$-SAT, I can try to write it tomorrow if no one gives an answer before that. (Hopefully someone does, mine is not great.) | |
| Jul 27, 2020 at 15:21 | comment | added | Ville Salo | If I understand correctly that good means no sequence in the set is a union of shifts of others, I'm guessing you can ensure only one of the sequences has small enough support that it's possible to cover with the others, and then there should be some easy reduction. It's pretty much clear that goodness is (co-)NP-complete. (Even if not as I suggest here.) | |
| Jul 27, 2020 at 15:15 | history | edited | Rodrigo de Azevedo |
edited tags
|
|
| Jul 27, 2020 at 15:08 | comment | added | Ville Salo | Ok so should it say there always exist $\tau_i$ such that $s_i^{t_i}(\tau_i) = 1$ and $s_j^{t_j}(\tau_i) = 0$ for $i \neq j$? | |
| Jul 27, 2020 at 14:58 | comment | added | lchen | @VilleSalo $\tau_i$ allows locate the appropriate bit in the shifted sequence. | |
| Jul 27, 2020 at 14:56 | comment | added | lchen | I have reformulated the problem | |
| Jul 27, 2020 at 14:55 | comment | added | Ville Salo | And it seems picking the $\tau_i$ makes the shifting meaningless, so I still don't understand what you are after. | |
| Jul 27, 2020 at 14:55 | history | edited | lchen | CC BY-SA 4.0 |
added 4 characters in body
|
| Jul 27, 2020 at 14:51 | comment | added | Ville Salo | Why are 101 and 011 good? Shifting one gives 101, 101 so doesn't seem so. | |
| Jul 27, 2020 at 14:50 | comment | added | lchen | @Ville Salo I have reformulated the problem. Hope it is clear now. | |
| Jul 27, 2020 at 14:50 | comment | added | lchen | @kodlu I have reformulated the problem. Hope it is clear now. | |
| Jul 27, 2020 at 14:48 | history | edited | lchen | CC BY-SA 4.0 |
deleted 10 characters in body
|
| Jul 27, 2020 at 14:44 | history | edited | lchen | CC BY-SA 4.0 |
added 168 characters in body
|
| S Jul 27, 2020 at 12:28 | history | suggested | JoshuaZ | CC BY-SA 4.0 |
Grammar- I think this is what is meant?
|
| Jul 27, 2020 at 12:01 | review | Suggested edits | |||
| S Jul 27, 2020 at 12:28 | |||||
| Jul 27, 2020 at 11:45 | comment | added | kodlu | you need to parse your sentences or define the condition for success properly, too many such that... such that, given that... Write it out in equations. | |
| Jul 27, 2020 at 11:33 | history | asked | lchen | CC BY-SA 4.0 |