Timeline for Formalize ignorance
Current License: CC BY-SA 4.0
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 26, 2019 at 6:44 | history | edited | Martin Rubey | CC BY-SA 4.0 |
added 44 characters in body
|
| Feb 26, 2019 at 6:42 | comment | added | Martin Rubey | One proposal is to restrict the amount of working memory available as in @James answer. However, I wonder whether one can unambiguously define the idea that an algorithm "visits" many elements of $B$. | |
| Feb 26, 2019 at 6:14 | comment | added | Martin Rubey | @FrançoisG.Dorais: yes, that is in fact my question! Here is another example, taken from mathoverflow.net/a/323827: Dyck paths of semilength $n$ with exactly one valley are in bijection with subsets of size $2$ in $\{1,\dots,n\}$. I would like to distinguish the algorithm that sorts the Dyck paths and the subsets and maps the Dyck path to the subset with the same index, from an algorithm that implements an 'explicit bijection', whatever that is. Note that in this case the two sets are rather small in terms of $n$, in contrast to the example with binary words. | |
| Feb 26, 2019 at 2:45 | comment | added | François G. Dorais | The second algorithm has a black box where there is a (not yet sorted) list of integer compositions of $n+1$ that comes out of nowhere. If I were to pick such a listing for use in the second algorithm I would probably pick the natural one given by the first algorithm, but then the two algorithms are essentially the same (with just a bit of extra overhead in the second algorithm). To play the devil's advocate: how are the two algorithms significantly different? (Except that the second is a slight generalization of the first.) | |
| Feb 25, 2019 at 22:09 | history | edited | Martin Rubey | CC BY-SA 4.0 |
deleted 2 characters in body
|
| Feb 25, 2019 at 22:08 | answer | added | James | timeline score: 1 | |
| Feb 25, 2019 at 22:05 | history | edited | Martin Rubey | CC BY-SA 4.0 |
deleted 2 characters in body
|
| Feb 25, 2019 at 21:59 | comment | added | Martin Rubey | Yes :-) It's binary, after all! | |
| Feb 25, 2019 at 21:56 | comment | added | Aaron Meyerowitz | I assume that by $10$ you mean $1+1.$ | |
| Feb 25, 2019 at 19:00 | history | asked | Martin Rubey | CC BY-SA 4.0 |