Timeline for Replacing logician-constructive with combinatorist-constructive?
Current License: CC BY-SA 2.5
4 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 5, 2010 at 18:36 | comment | added | Joel David Hamkins | For example, randomized algorithms (see en.wikipedia.org/wiki/Randomized_algorithm) were once regarded as non-standard, but are now completely classical methods, in comparison with more esoteric current considerations, such as quantum computation. | |
| Jun 5, 2010 at 17:40 | comment | added | Joel David Hamkins | Those subtle distinctions you mention, such as the difference between average case complexity and worst-case complexity, are not neglected and are also well studied. For example, see en.wikipedia.org/wiki/Generic-case_complexity. | |
| Jun 5, 2010 at 17:15 | comment | added | Jacques Carette | There are a plethora of algorithms which are worst-case doubly-exponential which, in practice, often terminate quickly (Groebner bases being the obvious example). Algorithms in $n^17$ for even moderate n will effectively never terminate. So, in practice, the useful classes are much more subtle than those which theoreticians have decided to study, IMHO. Similarly all sorts of undecidable problems have (large!) decidable fragments [like Halting, which you know better than I do]. | |
| Jun 5, 2010 at 11:46 | history | answered | Joel David Hamkins | CC BY-SA 2.5 |