« first day (2760 days earlier)      last day (1328 days later) » 

7:58 AM
Just posting a summary in case somebody wants later check when creation or removal or a tag was mentioned in this chatroom.
BTW this tag already appeared some time ago:
May 7 '20 at 11:40, by Martin Sleziak
A tag called was created, but relatively quickly removed: https://mathoverflow.net/posts/359612/revisions
One deleted questions with (at the moment): data.stackexchange.com/mathoverflow/query/883845/…
It is from December 2020: mathoverflow.net/questions/378092/…
The tag was around for a long time - the oldest occurrence that I see is from 2009: mathoverflow.net/posts/4953/revisions
22
Q: Super-linear time complexity lower bounds for any natural problem in NP?

RuneDo we know any problem in NP which has a super-linear time complexity lower bound? Ideally, we would like to show that 3SAT has super-polynomial lower bounds, but I guess we're far away from that. I'd just like to know any examples of super-linear lower bounds. I know that the time hierarchy the...


« first day (2760 days earlier)      last day (1328 days later) »