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 theorem gives us problems which can be solved in O(n^3) but not in O(n^2), etc. Thus I put the word "natural" in the question. I ask for problems in NP, because otherwise someone would give examples of EXP-complete problems. I know there are time-space tradeoffs for some problems in NP. I don't know if any of them imply a super-linear time complexity lower bound though.