Timeline for P decision problem that potentially requires at least $\Omega(n \log n)$ in the Turing model?
Current License: CC BY-SA 3.0
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 26, 2017 at 12:47 | comment | added | Albert Hendriks | I was under the impression that the best-known lower bound for NP problems was O(n) or slightly above. I was wrong. So I was actually looking for a decision problem that can be solved in O(n log n) but not in O(n). | |
| Jun 26, 2017 at 12:43 | vote | accept | Albert Hendriks | ||
| Jun 26, 2017 at 5:07 | comment | added | D.W.♦ | @YuvalFilmus, OK, thanks for explaining and for the correction -- I misunderstood the time hierarchy theorem. | |
| Jun 26, 2017 at 4:13 | history | edited | D.W.♦ | CC BY-SA 3.0 |
deleted 227 characters in body
|
| Jun 26, 2017 at 0:44 | comment | added | Yuval Filmus | The proof of the time hierarchy theorem is constructive, and you can extract a problem which requires more than $n\log n$ time. It just isn't so natural. | |
| Jun 25, 2017 at 23:27 | history | answered | D.W.♦ | CC BY-SA 3.0 |