Timeline for Computational complexity of fractions multiplication puzzle
Current License: CC BY-SA 4.0
17 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 10, 2019 at 21:12 | comment | added | Gerhard Paseman | It may be worth examining the simple version of your puzzle where all n's are powers of two and all d's are 1. The pseudo-polynomial solution of subset sum might become polynomial for you. Gerhard "Prefers Working The Easy Cases" Paseman, 2019.01.10. | |
| Jan 10, 2019 at 21:10 | comment | added | Mohammad Al-Turkistany | @BenBurns I suggest that my puzzle is strongly NP-complete (not Integer factorization ). | |
| Jan 10, 2019 at 21:05 | comment | added | Ben Burns | Integer factorization is strongly believed not to be NP-complete | |
| Jan 10, 2019 at 21:02 | comment | added | Mohammad Al-Turkistany | @GerhardPaseman My guess is that it is strongly NP-complete. | |
| Jan 10, 2019 at 20:54 | comment | added | Mohammad Al-Turkistany | @GerhardPaseman The input to my puzzle is not in exponent form. | |
| Jan 10, 2019 at 20:18 | comment | added | Gerhard Paseman | Only if you take the representation of expanding it out. If you keep it in exponent form there is no expansion. For your problem, you could do a similar reduction, and find that the size of the largest exponent and the number of terms determine a running time. If that bothers you, then consider my version of your puzzle where the n's and d's are given by their prime factorization. My version is at least as hard as subset sum. What does that make your version? Gerhard "My Guess Is Even Harder" Paseman, 2019.01.10. | |
| Jan 10, 2019 at 20:11 | comment | added | Mohammad Al-Turkistany | @GerhardPaseman But aren't you producing an exponentially larger instance? | |
| Jan 10, 2019 at 20:07 | comment | added | Gerhard Paseman | I see flipping as turning t to -t. I believe subset sum (finding a subset of the vector so that the subset sums to N) is equivalent to this, and that the reduction preserves the problem hardness. Gerhard "Yes, I'm Dealing With It" Paseman, 2019.01.10. | |
| Jan 10, 2019 at 19:50 | comment | added | Mohammad Al-Turkistany | @GerhardPaseman You are not dealing with flipping operation! | |
| Jan 10, 2019 at 19:46 | comment | added | Mohammad Al-Turkistany | The solution to the given instance is to flip the 1st, 4th, and the 5th fractions. | |
| Jan 10, 2019 at 19:33 | history | edited | Mohammad Al-Turkistany | CC BY-SA 4.0 |
added 2 characters in body
|
| Jan 10, 2019 at 19:28 | comment | added | Gerhard Paseman | Take an integer vector (or multiset) with sum of components 2N. Reduce to your problem by sending component t to (2/3)^t. Gerhard "This Is A Simple Reduction" Paseman, 2019.01.10. | |
| Jan 10, 2019 at 19:14 | history | edited | Mohammad Al-Turkistany | CC BY-SA 4.0 |
added 49 characters in body
|
| Jan 10, 2019 at 19:02 | comment | added | Mohammad Al-Turkistany | @GerhardPaseman I do not see an easy reduction. Please post your answer. | |
| Jan 10, 2019 at 18:59 | history | edited | Mohammad Al-Turkistany | CC BY-SA 4.0 |
added 49 characters in body
|
| Jan 10, 2019 at 18:54 | comment | added | Gerhard Paseman | How is this different from subset sum or partition? Isn't there an easy reduction? Gerhard "Just Use Many More Fractions" Paseman, 2019.01.10. | |
| Jan 10, 2019 at 18:50 | history | asked | Mohammad Al-Turkistany | CC BY-SA 4.0 |