Timeline for Why are those very similar languages in a different complexity class?
Current License: CC BY-SA 4.0
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 19, 2019 at 15:38 | history | edited | D.W.♦ | CC BY-SA 4.0 |
added 329 characters in body
|
| Apr 19, 2019 at 9:23 | comment | added | Raphael | @Evil No, it would mean that the problem space is truly that huge, preventing simple algorithms from working. D.W. says nothing about a complexity lower bound, which we don't know. | |
| Apr 18, 2019 at 23:04 | comment | added | Evil | @Raphael Theta here would mean that there doesn't exist algorithm that can test it faster, but it is possible to test in c*k time in the best case. | |
| Apr 18, 2019 at 22:10 | comment | added | Raphael | You need a $\Theta$ there. ;) | |
| Apr 18, 2019 at 16:52 | history | answered | D.W.♦ | CC BY-SA 4.0 |