MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

2 clarified question

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.

(To address a question below about machine models, consider either multitape Turing machines or the RAM model.)

1

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