Timeline for NP-hardness of a sequence problem
Current License: CC BY-SA 4.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 29, 2020 at 7:26 | vote | accept | lchen | ||
| Jul 28, 2020 at 16:34 | history | edited | Ville Salo | CC BY-SA 4.0 |
edited body
|
| Jul 28, 2020 at 16:33 | comment | added | Ville Salo | Dunno what to clarify about the next paragraph (the one about $b_i$s I guess), except I'll fix a typo. | |
| Jul 28, 2020 at 16:30 | comment | added | Ville Salo | The sequences $a_i$ are a simple set of sequences such that one is not covered by a union of others. I doubt the quadratic length is optimal, but the proof is very simple algebra for them (I wrote it). | |
| Jul 28, 2020 at 16:28 | comment | added | Ville Salo | If $s_1$ is the only one that could be covered, I just have to make sure, it's coverable iff the SAT instance is solvable. Otherwise I'd have to think about all $n$ sequnces. | |
| Jul 28, 2020 at 14:59 | comment | added | lchen | Thank you so much. Although I can see the intuition and logic of relating the problem to SAT, I fail to understand the intuition of proving $s_i$ as the only possible bad index, and the notion of $a_i$ (and the next paragraph). | |
| Jul 28, 2020 at 7:05 | history | answered | Ville Salo | CC BY-SA 4.0 |