Timeline for Conditions under which the 3-partition problem is not strongly NP-complete?
Current License: CC BY-SA 4.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 19, 2019 at 16:40 | comment | added | Adam Ierymenko | Input would be random (hashes, etc.) so the average case is what matters. A heuristic that speeds up some cases wouldn't help much, especially if it slows down others. No way to bias the input as it would be output from a cryptographic hash or cipher. | |
| Nov 17, 2019 at 10:21 | comment | added | Narek Bojikian | But then you should make sure that the generated instances are hard, i.e. do not all belong to a strict case or have something in common that makes the problem easy. For instance, I mentioned that even if each word is one letter it is hard. However, if every sentence is one word you can solve it greedily if sentences do not repeat and with dynamic programming if they do. So just make sure to build general hard instances with alphabet/sentences/words big enough. | |
| Nov 17, 2019 at 0:03 | comment | added | Adam Ierymenko | Thanks. I didn't mention it but what I'm looking for here is actually a "reliably slow" problem for applications like a randomness beacon or password hashing. It wouldn't be used directly for crypto but within a construct to make brute forcing impractical. There are other functions of course like ModSqrt, balloon hashing, huge memory lookup tables, forcing a large in-memory sort, etc., but I'm just looking for simpler or novel alternatives. This one is neat because it seems reliably slow yet trivially verifiable (check to see if the sets add to the same value). | |
| Nov 16, 2019 at 3:10 | comment | added | Narek Bojikian | For more infos about this kernel check "Parameterized Algorithms" book by Cygan et. al. | |
| Nov 16, 2019 at 3:10 | comment | added | Narek Bojikian | Not really. The best I can tell is the polynomial kernel for the d-set packing which is a generalization of 3d-matching which is a generalization (actually equivalent) to set partitioning. The problem is that even though the running time is polynomial in $n$ (due to reduction rules) it is polynomial in $k$ which is the size of the output. In our case we are looking for a perfect matching and hence $k = n/3$ so this result does not help here. | |
| Nov 16, 2019 at 2:47 | comment | added | Adam Ierymenko | Are you aware of any good work on parameterized, randomized, or heuristic algorithms for this particular problem? | |
| Nov 16, 2019 at 2:46 | vote | accept | Adam Ierymenko | ||
| Nov 16, 2019 at 2:08 | history | answered | Narek Bojikian | CC BY-SA 4.0 |