Timeline for Worst known algorithm in terms of Big-O (more precisely Big-theta)?
Current License: CC BY-SA 4.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 23, 2022 at 10:04 | history | edited | Martin Sleziak | CC BY-SA 4.0 |
http -> https (the question was bumped anyway)
|
| May 19, 2011 at 22:31 | comment | added | Joel David Hamkins | Ah, I see now that "elementary recursive" is a very limited class: en.wikipedia.org/wiki/ELEMENTARY. | |
| May 19, 2011 at 16:57 | comment | added | user5810 | @Joel: Yes, but it does not make it elementary recursive. | |
| May 19, 2011 at 16:56 | comment | added | user5810 | @Thierry: Yes, that's what the article says. | |
| May 19, 2011 at 12:41 | comment | added | Joel David Hamkins | Thierry, Tarski's original algorithm was an elimination of quantifiers argument: given a sentence, he applied his recursive quantifier elimination procedure and ended up with a quantifier-free assertion, whose truth can be easily decided. This makes his original algorithm definitely recursive, even primitive recursive, but it was horribly iterated exponential time. | |
| May 19, 2011 at 12:36 | history | edited | Kevin O'Bryant | CC BY-SA 3.0 |
created hyperlink
|
| May 19, 2011 at 12:11 | comment | added | Thierry Zell | Isn't it the case that in Tarski's original formulation, the complexity is not even elementary recursive? | |
| May 19, 2011 at 10:26 | history | answered | user5810 | CC BY-SA 3.0 |