Timeline for Can algorithm discovery be brute forced?
Current License: CC BY-SA 3.0
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 18, 2017 at 12:33 | review | First posts | |||
| Apr 18, 2017 at 16:28 | |||||
| Apr 16, 2017 at 14:58 | comment | added | David Richerby | The question is about finding polynomial time algorithms. It's not, in principle, a problem if finding the algorithm takes a long time, since you only need to find it once. Note also that P-vs-NP doesn't have much impact on exponential search problems: you shouldn't associate NP with exponential time, because that's not what it is: we believe that NP is strictly weaker than EXP. | |
| Apr 16, 2017 at 8:41 | comment | added | Andrey Gurevich | It's not about hardware and how many machines do you have it's about your algorithm complexity. If you preform some kind of brute force search you can't complete it on any machine unless the number of bits is really small. There are many problems with your proposal besides it being too expansive. For a specific problem you will get to a specific answer of this problem but not a general one. Example: You want to sort an array, you may find the fastest way to sort this specific array but it won't work a different array. | |
| Apr 16, 2017 at 7:51 | comment | added | Adam Zerner |
I don't think it's self evident that the $2^n$ space of potential solutions is impractical. It seems to me to depend on all of those parameters. In particular, I don't know much about high performance computing, and where the field is headed. Maybe with enough power it really is doable. I also don't know much about what kinds of intelligent improvements could be made. Or whether my choice of n was sensible.
|
|
| Apr 16, 2017 at 7:08 | history | answered | Andrey Gurevich | CC BY-SA 3.0 |