MO editors' lounge

« first day (2760 days earlier) ← previous day next day → last day (1153 days later) »

7:58 AM

new-tag deleted-tag upper-bounds - see above

new-tag frobenius-map and topological-semigroups-and-monoids - see above

deleted-tag frobenius

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

new-tag deleted-tag A tag called upper-bounds was created, but relatively quickly removed: https://mathoverflow.net/posts/359612/revisions

Posts where upper-bounds was added/removed (with editors): data.stackexchange.com/mathoverflow/query/1105163/… data.stackexchange.com/mathoverflow/query/1038474/…

One deleted questions with upper-bounds (at the moment): data.stackexchange.com/mathoverflow/query/883845/…

It is from December 2020: mathoverflow.net/questions/378092/…

Posts where lower-bounds was added/removed (with editors): data.stackexchange.com/mathoverflow/query/1105163/… data.stackexchange.com/mathoverflow/query/1038474/…

Most frequent taggers/removers for lower-bounds: data.stackexchange.com/mathoverflow/query/1146497/… data.stackexchange.com/mathoverflow/query/1038477/…

Deleted questions with lower-bounds: data.stackexchange.com/mathoverflow/query/883845/…

The tag lower-bounds was around for a long time - the oldest occurrence that I see is from 2009: mathoverflow.net/posts/4953/revisions

Q: Super-linear time complexity lower bounds for any natural problem in NP?

Do 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...