Timeline for Set of K elements with minimum cost and GCD=1
Current License: CC BY-SA 4.0
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 15 at 14:14 | comment | added | Narek Bojikian | True, my algorithm is not polynomial when weights are given in binary. It is quite close to the Knapsack problem as well, I just restricted to the given constraints (small values, so pseudoplynomial is enough) | |
| Nov 14 at 19:53 | comment | added | user2357112 | @minhquýlê: Primes are too common for that to be a problem - the nth prime is around $n \log(n)$. | |
| S Nov 14 at 19:50 | history | suggested | minh quý lê | CC BY-SA 4.0 |
Add "if and only if" condition of the reduction
|
| Nov 14 at 19:42 | comment | added | minh quý lê | I think mapping and computing prime numbers have an issue. There is a theorem about distance between 2 consecutive prime numbers, i.e. $p_2-p_1$, that all such distance are possible, so I worry when $|U|$ is large enough, $|U|$th primes is larger than $2^{2^{|U|}}$, implying that the reduction is not polynomial. | |
| Nov 14 at 19:33 | review | Suggested edits | |||
| S Nov 14 at 19:50 | |||||
| Nov 14 at 19:00 | history | answered | user2357112 | CC BY-SA 4.0 |