Timeline for What is this algorithm?
Current License: CC BY-SA 3.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 24, 2015 at 18:48 | comment | added | liggiorgio | You didn't specify your algorithm shall satisfy any level of complexity. Your problem is interesting but I can't keep thinking about a better solution. I strongly suggest you to take a look at "divide-and-conquer" and related metodologies and algorithms, because only by deeply understanding it you will find out a way to make a better algorithm for your purposes. | |
| Nov 23, 2015 at 10:21 | comment | added | ibi0tux |
Your way of doing this sounds good except its complexity is linear since it will call the oracle C times (with C the cardinality of A, actually 1+C-1). The complexity of the oracle is also linear you're right, which means the global complexity is polynomial which is unacceptable for my needs. I think we can reduce the number of calls to oracle to something in terms of n*log(C) and I wish there was a proven algorithm for this.
|
|
| Nov 21, 2015 at 19:08 | history | edited | liggiorgio | CC BY-SA 3.0 |
deleted 554 characters in body
|
| Nov 21, 2015 at 18:29 | comment | added | liggiorgio | I got your point, I'm editing my current answer to explain a new possible solution. | |
| Nov 20, 2015 at 17:07 | comment | added | ibi0tux | Your answer is interesting. What's a little more complicated is that we have to consider that th minimum input size for the oracle is huge and thus the subsets we have to provide contain a lot of assertions. My thoughts were to work with pairs of sets, and rather generating power set of A, I would generate all combinations of the items in two distinct subsets. But this is obiously not optimal (in the worst case only the half of those combination would suffice). I'm editing my post to give more details. | |
| Nov 20, 2015 at 16:35 | review | First posts | |||
| Nov 20, 2015 at 16:44 | |||||
| Nov 20, 2015 at 16:34 | history | answered | liggiorgio | CC BY-SA 3.0 |